细胞自动机

✍ dations ◷ 2025-04-02 10:36:13 #细胞自动机
细胞自动机(英语: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类可划分为稳定(定点)和振荡(周期)规则两个小组。

相关

  • 地舌菌纲地舌菌纲(学名:Geoglossomycetes)是子囊菌门盘菌亚门的一个纲,为一个单型的分类元,其下只有地舌菌目(Geoglossales)一个单型目,而地舌菌目亦只有地舌菌科(Geoglossaceae)一个科。地舌
  • 基群基群(英语:Basal)是生物学中的术语,专指在亲缘关系学中最早分离出去的大型演化支,并且通常会位于亲缘分支分类法最底层处,是其它后来才分化出去的演化支的外类群。许多生物学家(特
  • 法规法规(英语:Statute;制定法)是由立法机关正式明文写成的律例,用以管治国家、城市或地方。一般而言,法规的作用在于命令或禁止一类事物、或用作颁布一项政策。法规一词通常用以区别
  • 同一时期的全球历史后古代史(也称前现代史)是西方历史学划分出来的一段时期的历史。欧洲历史学界一般把历史分为三个阶段——古代、中世纪和近代,而后古代与中世纪是完全对应的,它位于古代史与现代
  • 硫酸铜硫酸铜,化学式CuSO4,无水为白色粉末,或因不纯而呈淡灰绿色,是可溶性铜盐。硫酸铜常见的形态为其结晶体,一水合硫酸四水合铜([Cu(H2O)4]SO4·H2O,五水合硫酸铜)为蓝色固体,故俗名为蓝矾
  • ZZ, z是拉丁字母中的第26个字母,也是最后一个字母。这个字母的英语念法有2种:英国等大部分英语口音会念作.mw-parser-output .IPA{font-family:"Charis SIL","Doulos SIL","Lin
  • 布列塔尼半岛布列塔尼半岛(法语:Bretagne,发音:.mw-parser-output .IPA{font-family:"Charis SIL","Doulos SIL","Linux Libertine","Segoe UI","Lucida Sans Unicode","Code2000","Gentium"
  • 獴科(学名:Herpestidae),哺乳纲食肉目的一科,外形较像猫,有猫鼬的别称。包括獴亚科及缟獴亚科两个亚科。以下几属过去归为獴科,现在被分入食蚁狸科(Eupleridae):
  • 林同炎林同炎(英语:Tung-yen Lin 或 T. Y. Lin,1912年11月14日-2003年11月15日),原名林同棪,美籍华裔结构工程师。林同炎出生于福建省福州,是家中第4个小孩(共有11个),后来在北京成长。他的父
  • 索姆省索姆省(法语:Somme)是法国上法兰西大区所辖的省份,位于法国北部,由境内的索姆河得名。该省编号为80。第一次世界大战中著名的索姆河战役就发生于此。5个海外省及大区