首页 >
细胞自动机
✍ dations ◷ 2025-07-02 11:21:43 #细胞自动机
细胞自动机(英语: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类可划分为稳定(定点)和振荡(周期)规则两个小组。
相关
- 疣微菌门疣微菌门(Verrucomicrobia)是一门被划出不久的细菌,包括少数几个被识别的种类,主要被发现于水生和土壤环境,或者人类粪便中。还有很多未被成功培养的种类是和真核宿主共生的,包括
- 单系群单系群(英文:Monophyletic group,也称为单系类群)在支序分类中指的是一个分类单元(Taxon),其中的所有物种,只有一个共同的祖先,而且它们就是该祖先的所有后代。单系群也可以被这样定
- 亚里士多德亚里士多德(希腊语:Αριστοτέλης,Aristotélēs,前384年-前322年3月7日),古希腊哲学家,柏拉图的学生、亚历山大大帝的老师。他的著作牵涉许多学科,包括了物理学、形而上学
- Boston新英格兰波士顿(英语:Boston)为美国马萨诸塞联邦(英语:Commonwealth (U.S. state))首府,占地面积 48平方英里(124 km2),2018年居民总数为694,583位,是马萨诸塞乃至新英格兰地区人口最
- 美国短吻鳄美国短吻鳄(学名:Alligator mississippiensis),又称密西西比河鳄,是西半球大型的鳄鱼物种。雄性鳄长达4米以上,雌的不到3米。幼鳄为黑色,身上点缀著无规律的黄色横向带纹,到了成年时
- 高温超导高温超导(High-temperature superconductivity,High Tc)是一种物理现象,指一些具有较其他超导物质相对较高的临界温度的物质在液态氮的环境下产生的超导现象。高温超导体(High-te
- 四重溪温泉坐标:22°05′43″N 120°44′45″E / 22.0952585°N 120.7457938°E / 22.0952585; 120.7457938四重溪温泉位于台湾屏东县车城乡。依地质分类,属于沉积岩温泉。以前居民出入
- P-过程P-过程是发生在超新星的核心坍缩时进行的核合成(参见超新星核合成),对比铁重且富含质子原子核的产生有不可忽视的贡献。当P-过程在著名的B2FH理论在1957年被提出时,这个过程的物
- 福楼拜古斯塔夫·福楼拜(法语:Gustave Flaubert,1821年12月12日-1880年5月8日),生于法国鲁昂,法国文学家,世界文学名著《包法利夫人》的作者。福楼拜出生于法国西北部诺曼底地区的鲁昂,父亲
- 吉尔·德勒兹吉尔·德勒兹(法语:Gilles Louis René Deleuze;1925年1月18日-1995年11月4日),法国后现代主义哲学家。德勒兹出生在法国首都巴黎,一九四四年中学毕业后进入巴黎索邦大学哲学系就读