细胞自动机

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

相关

  • 环丙沙星环丙沙星(Ciprofloxacin)是第二代氟喹诺酮类化合广效抗生素(英语:Broad-spectrum antibiotic),可对抗多种病原菌。治疗范围包含骨骼感染、关节感染、腹部感染,以及特定几种感染性肠
  • 铝离子电池铝离子电池(Aluminium-ion battery)是一类可充电电池,放电时,铝离子从阴极移动到阳极;充电时,铝离子又回到阴极。铝离子电池与锂离子电池功能相似,但由于组成和结构不同,电能输出水
  • 高压氧高压氧治疗,或简称高压氧,英文:Hyperbaric oxygen therapy (HBOT) ,乃医学上利用高压的氧气来提供治疗的方式。高压氧治疗利用了几个原理:高压氧最主要的治疗适应症包括:以上除一
  • 法医人类学法医人类学(英语:Forensic anthropology),是体质人类学与人骨学(osteology,对人类骨骼的研究)运用于法律环境下的应用科学,往往是在刑事案件中,受害人尸骸的分解程度较深的阶段。法医
  • 左肺动脉肺动脉肺部的动脉,是人体内循环系统中肺循环的重要组成部分。与其他动脉不同,肺动脉中运输的是去氧血而非带氧血液。肺动脉携带去氧血由右心室打出,在肺部交换气体后,打入左心房
  • Prescription Only (S4)《药物和毒物的统一调度标准》(英语:Standard for the Uniform Scheduling of Medicines and Poisons,SUSMP)是澳大利亚政府药物管理局(英语:Therapeutic Goods Administration)出
  • 原始生命体原初生命体(英语:protocell 或 protobiont)被认为有可能是原核细胞的祖先,是由膜或膜样的结构包围非生物生产的有机分子的集合体。其表现出一些与生命相关的属性,如简单的繁殖,代
  • 麦克米伦出版公司麦克米伦出版公司(Macmillan Publishers Ltd.)是六大出版商之一,由苏格兰人丹尼尔及亚历山大·麦美伦两兄弟于1843年在英国伦敦成立,前英国首相哈罗德·麦美伦于卸任首相后曾担
  • 司陶特世涛啤酒(英语:Stout),又称烈性啤酒、烈性黑啤酒,一种深色的啤酒,由烘焙过的麦芽或是大麦、啤酒花、水及酵母所制成。它源自于波特啤酒(Porter),酒精含量约7%至8%,口味较强烈。世涛源
  • DNA超螺旋DNA超螺旋(英语:DNA supercoil)指双螺旋环状DNA扭转后再进一步地扭转,产生的结构类似电话线被扭转之后的样子。 所谓的超螺旋就是:原本已经是螺旋形态的结构进一步再次螺旋缠绕。