Loading AI tools
来自维基百科，自由的百科全书
細胞自動機（英語：Cellular automaton），又稱格狀自動機、元胞自動機，是一種離散模型，在可计算性理論、數學及理論生物學都有相關研究。它是由無限個有規律、堅硬的方格組成，每格均處於一種有限狀態。整個格網可以是任何有限維的。同時也是離散的。每格於t時的態由t-1時的一集有限格（這集叫那格的鄰域）的態決定。每一格的「鄰居」都是已被固定的。（一格可以是自己的鄰居。）每次演進時，每格均遵從同一規矩一齊演進。
就形式而言，細胞自動機有三個特徵：
一个标准的細胞自動機（）由元胞、元胞状态、邻域和状态更新规则构成。用数学表示为[1]：
其中L为元胞空间；d为元胞自动机内元胞空间的维数；S是元胞有限的、离散的状态集合；N为某个邻域内所有元胞的集合；f为局部映射或局部规则。
元胞空间是元胞所分布的空间网点的集合。理论上元胞空间在各个维向上是无限延伸的，为了能够在计算机上实现，而定义了边界条件，包括周期型、反射型和定值型[2]。
一个元胞通常在一个时刻只有取自一个有限集合的一种状态，例如{0,1}。元胞状态可以代表个体的态度，特征，行为等[3]。在空间上与元胞相邻的细胞称为邻元，所有邻元组成邻域。
細胞自動機最早由美籍數學家冯·诺依曼（John von Neumann）在1950年代为模拟生物细胞的自我复制而提出，但是并未受到学术界重视。直到1970年，英國數學家约翰·何顿·康威（John Horton Conway）设计了生命游戏並經馬丁·葛登在《科學美國人》雜誌上介紹，才吸引了科学家们的注意。此后，英國學者史蒂芬·沃爾夫勒姆（Stephen Wolfram）对初等元胞机256种规则所产生的模型进行了深入研究，并用熵來描述其演化行为，将細胞自動機分为平稳型、周期型、混沌型和复杂型[4]。
史蒂芬·沃爾夫勒姆在《一种新科学》和几篇从80年代中期开始的论文中定义了四类细胞自动机和其他几个简单的计算模型。元胞自动机的早期研究往往试图确定具体规则的模式类型，他提出的分类是对规则本身分类的第一次尝试。按照复杂性分类的秩序：
根据史蒂芬·沃爾夫勒姆的說法，这些定义在本质上是定性的但是任有解释一些空间。“……几乎任何一般的分类方案都有不可避免的情况，比如说根据不同的定义会被分配到不同的类里。因此细胞自动机也是这样：偶尔有规则……显示不同类的一些特点。”[7]他的分类已经与一个类具有压缩长度输出的元胞自动机相匹配。[8]
已经有人在尝试进行细胞自动机的正式严格分类根据史蒂芬·沃爾夫勒姆的分类。例如，Culik和Yu提出三种定义的类（并且第四个和它们不同），有时被称为Culik-Yu 类；能够被分到这种类里的问题被证明是不可判定的。[9][10][11]史蒂芬·沃爾夫勒姆的2类可划分为稳定（定点）和振荡（周期）规则两个小组。[12]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
