首页 >
细胞自动机
✍ dations ◷ 2025-04-03 12:11:24 #细胞自动机
细胞自动机(英语:Cellular automaton),又称格状自动机、元胞自动机,是一种离散模型,在可计算性理论、数学及理论生物学都有相关研究。它是由无限个有规律、坚硬的方格组成,每格均处于一种有限状态。整个格网可以是任何有限维的。同时也是离散的。每格于t时的态由t-1时的一集有限格(这集叫那格的邻域)的态决定。每一格的“邻居”都是已被固定的。(一格可以是自己的邻居。)每次演进时,每格均遵从同一规矩一齐演进。就形式而言,细胞自动机有三个特征:一个标准的细胞自动机(
A
{displaystyle A}
)由元胞、元胞状态、邻域和状态更新规则构成。用数学表示为:其中L为元胞空间;d为元胞自动机内元胞空间的维数;S是元胞有限的、离散的状态集合;N为某个邻域内所有元胞的集合;f为局部映射或局部规则。元胞空间是元胞所分布的空间网点的集合。理论上元胞空间在各个维向上是无限延伸的,为了能够在计算机上实现,而定义了边界条件,包括周期型、反射型和定值型。一个元胞通常在一个时刻只有取自一个有限集合的一种状态,例如{0,1}。元胞状态可以代表个体的态度,特征,行为等。在空间上与元胞相邻的细胞称为邻元,所有邻元组成邻域。细胞自动机最早由美籍数学家冯·诺依曼(John von Neumann)在1950年代为模拟生物细胞的自我复制而提出的。但是并未受到学术界重视。直到1970年,任教于剑桥大学的英国数学家约翰·何顿·康威(John Horton Conway)设计了生命游戏,经马丁·葛登在《科学美国人》杂志上介绍,才吸引了科学家们的注意。此后,英国学者史蒂芬·沃尔夫勒姆(Stephen Wolfram)对初等元胞机256种规则所产生的模型进行了深入研究,并用熵来描述其演化行为,将细胞自动机分为平稳型、周期型、混沌型和复杂型。史蒂芬·沃尔夫勒姆在《一种新科学》和几篇从80年代中期开始的论文中定义了四类细胞自动机和其他几个简单的计算模型。元胞自动机的早期研究往往试图确定具体规则的模式类型,他提出的分类是对规则本身份类的第一次尝试。按照复杂性分类的秩序:根据史蒂芬·沃尔夫勒姆的说法,这些定义在本质上是定性的但是任有解释一些空间。“……几乎任何一般的分类方案都有不可避免的情况,比如说根据不同的定义会被分配到不同的类里。因此细胞自动机也是这样:偶尔有规则……显示不同类的一些特点。”他的分类已经与一个类具有压缩长度输出的元胞自动机相匹配。已经有人在尝试进行细胞自动机的正式严格分类根据史蒂芬·沃尔夫勒姆的分类。例如,Culik和Yu提出三种定义的类(并且第四个和它们不同),有时被称为Culik-Yu 类;能够被分到这种类里的问题被证明是不可判定的。史蒂芬·沃尔夫勒姆的2类可划分为稳定(定点)和振荡(周期)规则两个小组。
相关
- 麻醉在医学领域(尤其是外科、牙医学)中,麻醉(英语:anesthesia或anaesthesia)是一种临时失去意识和感觉的状态。它可能包括疼痛减轻、瘫痪(指肌肉放松)、失去记忆和无意识。
- 韦斯顿电池韦斯顿电池是一种原电池,1893年由英国化学家爱德华·韦斯顿(Edward Weston)发明。由于其高度稳定的电动势,多用于实验室中电位计的校准。1911年该电池被采纳为电动势的国际标准
- 2015年至2016年冬中国北京雾霾事件2015年至2016年冬中国北京雾霾事件,是指2015年入冬后起始于2015年12月8日重度雾霾事件,北京在污染期间曾多次启动空气重污染红色预警。北京首次空气重污染红色预警从2015年12
- 黑山县黑山县是中国辽宁省锦州市下辖的一个县。位于辽宁省西部。明代名为镇远堡,清初又叫小河山,小黑山。县城东北隅有小黑山,古上帝庙建于其颠。该山虽不甚高,但登临其上,远望群山,近瞻
- 巴尔奇克巴尔奇克 (保加利亚语:Балчик)是位于保加利亚东北部的城市。地处多布里奇州,黑海沿岸。巴尔奇克是海滨度假胜地。位于瓦尔纳东北42公里处。市区建在黑海沿岸的多布罗加台
- 吸血蝠吸血蝠亚科(英文:Vampire bat)是属于脊索动物门哺乳纲翼手目叶口蝠科的亚科,含有吸血蝠、毛腿吸血蝠和白翼吸血蝠三个种,都原产于美洲。亚科名“Desmodontinae”出自古希腊文词“
- 主题分析主题分析(英语:Thematic analysis)是定性研究中最为常见的一种形式。它强调在数据中精确定位、检查和记录主题或模式。主题(英语:themes)是跨数据集的模式(英语:patterns),这些模式对
- 东亚传统东亚传统度量衡,通称度量衡,指源于中国,广泛应用于东亚各国的传统计量体系。日本多称为尺贯法,也称尺间法,其中“尺”为东亚通用的长度单位,“贯”在日本为质量单位,“间”为日本长
- 前苏格拉底哲学家前苏格拉底 · 古代 中世纪 · 文艺复兴 17世纪 · 18世纪 · 19世纪 · 20世纪 后现代 · 当代前苏格拉底哲学是西方哲学中,在苏格拉底之前的,或者是和苏格拉底
- 波河平原波河河谷或称波河平原、巴丹平原(意大利语:Pianura Padana 或 Val Padana)是意大利的主要平原和地理特征之一,也是欧洲的主要工农业产区,位于波河流域。它从阿尔卑斯山一直延伸