元胞自动机（一）
一、简介
1.1 入门：一个非常简单的 CA
1.2 CA能力概述
1.3 简史
2. 一些基本概念和结果
2.1 基本定义
2.2 Wolfram 分类方案
2.3 256条规则的类别
2.4 混沌边缘
2.5 更多维度的CA：生命的游戏
2.6 通用图灵机的生命
2.7 进一步CA
3.CA与哲学
3.1 CA与涌现
3.2 CA和自由意志
3.3 CA和计算哲学
3.4 CA 作为现实模型
4. 结束语
参考书目
学术工具
其他互联网资源
相关条目
一、简介
1.1 入门：一个非常简单的 CA
我们用一个简单的例子来介绍CA。将自动机视为简单元素（单元）的一维网格。他们每个人只能实例化两种状态之一；假设每个单元都可以打开或关闭。系统的演化由转换规则决定，被认为是在每个单元中实现的。在每个时间步，每个单元都会根据规则更新其状态，以响应其相邻单元发生的情况。
图1
图1
尽管 CA 是抽象的，但在开始时记住一个具体的实例会有所帮助。因此，可以将图 1 想象为代表高中教室的前排。每个方框代表一个戴帽子（黑色）或不戴帽子（白色）的学生。让我们做出以下两个假设：
帽子规则：如果坐在她左边和右边的两个同学中的一个或另一个（但不是两个）在当前班级中戴过帽子，则该学生将在下一堂课中戴该帽子（如果没有人戴帽子，帽子已经过时了；但如果邻居都戴的话，帽子现在就太流行了，不再流行了）。
第一堂课：早上第一节课，中间只有一个学生戴着帽子出现（见图2）。
图2
图2
图 3 显示了随着时间的推移会发生什么。连续的行代表后续类别随时间的演变。
图3
图3
图 3 可能会令人惊讶。显示的进化模式与基本法则（“帽子规则”）和本体论的简单性形成鲜明对比（因为就对象和属性而言，我们只需要考虑简单的细胞和两种状态）。系统的全局的、突现的行为取决于其局部的、简单的特征，至少在以下意义上：戴帽子的决定的规模（直接邻居）并不是有趣的模式变得明显的规模。
这个例子是 CA 吸引广大研究人员的典型例证：
即使对个体决策规则的完美了解也并不总是能让我们预测宏观结构。尽管我们拥有完整的微观知识，但我们还是会得到宏观的惊喜。 （爱泼斯坦 1999：48）
由于涌现的概念和微观-宏观相互作用在科学和哲学中具有如此重要的作用（参见附带性和涌现属性的条目；有关科学应用的示例，请参见 Mitchell 2009：2-13；Gell-Mann 1994：第 9 章），有人建议采用 CA 视角可以解决许多科学和概念难题。 Stephen Wolfram 甚至声称 CA 可以帮助我们解决哲学中长期存在的问题：
其中[哲学家解决的基本问题]包括关于知识的终极极限、自由意志、人类状况的独特性和数学的必然性的问题。在哲学史上，关于这些问题已经有很多论述。但不可避免的是，它只能通过当前关于事物应该如何运作的直觉来判断。但我在《一种新的科学》这本书中的发现带来了全新的直觉。 （沃尔夫拉姆 2002：10）
这些都是非常大胆的主张。为了评估它们，让我们仔细看看这个领域。
1.2 CA能力概述
上述课堂示例中令人惊讶的模式是由只有两个状态和一个简单规则的盒子生成的。人们可能想知道这样一个基本框架可以有多少种变化。为了解决这个问题，让我们首先考虑 Andrew Ilachinski 在他的文献综述中如何将 CA 应用范围缩小到四个主要领域，这将在本条目的其余部分中提到 (Ilachinski 2001: 7)：
(CA1)
作为强大的计算引擎。
(CA2)
作为离散动力系统模拟器。
(CA3)
作为研究模式形成和复杂性的概念工具。
(CA4)
作为基础物理的原始模型。
(CA1)强调CA执行计算。就像图灵机一样，它们可以用数学术语来指定，并在不同的物理系统中实现。然而，CA 有两个重要方面的特殊性。首先，与图灵机和冯·诺依曼架构的传统计算机不同，CA 以并行、分布式的方式进行计算。其次，计算几乎是“情人眼里出西施”：没有磁带，但单元状态的演变通常可以解释为有意义的计算过程（例如，可以使用白/黑单元对位进行编码）州）。受 CA 启发的计算硬件可以帮助解决重要的技术问题（参见 Ilachinski 2001：8），但除了工程问题之外，（CA1）还指出了主要的概念问题，例如如何严格比较通用图灵机和自动机（参见 Beraldo-de-Araújo 和 Baravalle 即将出版）以及这种比较的哲学含义（如果有的话）是什么（参见 Wolfram 2002：Ch. 12）。
(CA2) 包括 CA 在特定问题建模中的科学应用——仅举几例：城市演化 (Batty 2005)、Ising 模型 (Creutz 1986)、神经网络 (Franceschetti 等人 1992: 124–128)、晶格流体 (Barberousse & Imbert 2013)、安全性 (Ray et al. 2023 [其他互联网资源])、生物信息学（Xiao et al. 2011），甚至湍流现象（Chen et al. 1983）。例如，正如 Ilachinski 所说，湍流的离散模型表明
局部守恒定律的非常简单的有限动态实现能够在宏观尺度上精确地再现连续系统行为。 （伊拉钦斯基 2001：8）
（CA3）和（CA4）非常直接地进入哲学领域：至于（CA3），丹尼尔·丹尼特（Daniel Dennett）诉诸了我们下面描述的一个著名的自动机，康威的生命游戏，来表达他关于决定论和高级归因的观点。层次概念到涌现模式（Dennett 1991，2003）。至于 (CA4)，CA 可以通过代表量子场论的离散对应物（参见量子场论条目）替代标准连续框架来提供微观物理动力学的解释。但在这一领域，更哲学、更大胆的主张是，自然本身可能就是一个 CA：例如，爱德华·弗雷德金 (Edward Fredkin) 提出了他的“有限自然”假设，即我们的宇宙是一个自动机，在每个时间步骤，它都以数字方式运行。并在本地处理下一个时间步的状态（参见 Fredkin 1993）。除了弗莱德金的主张引起的兴趣之外，有趣的假设还引发了物理学和形而上学（什么是自然法？）、认识论（物理系统可预测性的极限是什么？）和信息哲学等交叉点的许多问题。 （信息在物理世界中的作用是什么？）。我们将在本文的第三部分中解决这些问题。
1.3 简史
CA之父是约翰·冯·诺依曼（von Neumann 1951）。冯·诺依曼致力于自我复制并试图提供生物发展的还原论理论，试图构想一个能够产生自身精确副本的系统。现在，生物学表面上似乎是流动性和连续动态的领域。但根据同事斯坦尼斯瓦夫·乌拉姆的建议，冯·诺依曼决定专注于离散的二维系统。冯·诺依曼的自动机不只是使用黑白细胞，而是使用 29 种不同的状态和相当复杂的动力学，并且能够自我复制。冯·诺依曼的 CA 也是历史上第一个被正式证明是通用计算机的离散并行计算模型，即能够模拟通用图灵机并计算所有递归函数（参见条目）。
六十年代初期，E.F. Moore (1962) 和 Myhill (1963) 证明了伊甸园定理，阐述了所谓伊甸园存在的条件，即，不能出现在 CA 晶格上的模式，除非初始条件。 Gustav Hedlund (1969) 在符号动力学框架内研究了元胞自动机。 1970 年，数学家约翰·康威 (John Conway) 推出了他前面提到的生命游戏 (Berkelamp, Conway, & Guy 1982)，可以说是有史以来最受欢迎的自动机，也是有史以来最简单的计算模型之一，被证明是通用计算机。 1977年，Tommaso Toffoli使用元胞自动机直接模拟物理定律，为可逆CA的研究奠定了基础（Toffoli 1977）。
Stephen Wolfram 在 20 世纪 80 年代的作品为将不断增长的 CA 追随者社区纳入科学版图做出了贡献。在一系列论文中，Wolfram 广泛探索了一维 CA，提供了其行为的第一个定性分类法，并为进一步研究奠定了基础。 Wolfram 推测一维 CA 的一个特定转换规则（称为规则 110）是通用的。猜想大约二十年后，马修·库克证明了规则 110 能够进行通用计算（Cook 2004；Wolfram 2002 也包含证明的草图）。
2. 一些基本概念和结果
2.1 基本定义
我们现在正在仔细研究 CA，重点关注具有哲学意义的模型和结果。尽管 CA 文献中的系统种类繁多，但人们可以通过调整定义其结构的四个参数来生成几乎所有 CA：
离散 n 维细胞晶格：我们可以拥有一维、二维、……、n 维 CA。晶格的原子成分可以具有不同的形状：例如，2D晶格可以由三角形、正方形或六边形组成。通常假设同质性：所有细胞在质量上都是相同的。
离散状态：在每个离散时间步长，每个细胞都处于一种且仅有一种状态，
σ
ε
Σ
,
Σ
�
ε
Σ
,
Σ
是一组有限基数
|
Σ
|
=
k
|
Σ
|
=
�
。
局部相互作用：每个细胞的行为仅取决于其局部细胞邻域内发生的情况（可能包括也可能不包括细胞本身）。具有相同基本拓扑的格子可能具有不同的邻域定义，如下所示。但值得注意的是，“远距离行动”是不允许的。
离散动力学：在每个时间步，每个单元根据确定性转换函数更新其当前状态
φ
：
Σ
n
→
Σ
�
：
Σ
�
→
Σ
映射邻域配置（n 元组的状态
Σ
Σ
） 到
Σ
Σ
。通常（尽管不一定）假设（i）更新是同步的，并且（ii）
φ
�
将前一个时间步的邻域状态作为时间步 t 的输入
t
-
1
�
-
1
。
例如，我们可以详尽地描述我们课堂示例中的自动机：
一条线上的方形单元格的一维晶格。
Σ
=
1
,
0
Σ
=
1
,
0
（1 = 黑色或戴帽子，0 = 白色或脱帽子），所以
|
Σ
|
=
2
|
Σ
|
=
2
。
每个单元格的邻域由两个最近的单元格组成。如果我们用整数索引单元格，那么
c
我
�
�
是单元格编号 i，则其邻域
c
我
�
�
是
氮
（
c
我
）
=
⟨
c
我
-
1
,
c
我
+
1
⟩
�
（
�
�
）
=
⟨
�
�
-
1
,
�
�
+
1
⟩
。
过渡规则
φ
�
很简单：在每个时间步 t，如果恰好有一个相邻细胞在 t 处为 1，则细胞状态为 1
t
-
1
,
0
�
-
1
,
0
否则。
CA 的规则可以表示为条件指令：“如果邻域是这个和这个，则转向状态 s”。我们可以写出一维 CA 规则的一般形式：
（规则1D）
σ
我
（
t
+
1
）
=
φ
（
σ
我
-
r
（
t
）
,
σ
我
-
r
+
1
（
t
）
,
……
,
σ
我
+
r
-
1
（
t
）
,
σ
我
+
r
（
t
）
）
（规则1D）
�
�
（
�
+
1
）
=
�
（
�
�
-
�
（
�
）
,
�
�
-
�
+
1
（
�
）
,
……
,
�
�
+
�
-
1
（
�
）
,
�
�
+
�
（
�
）
）
在哪里
σ
我
（
t
）
ε
Σ
=
{
0
,
1
,
……
,
k
-
1
}
�
�
（
�
）
ε
Σ
=
{
0
,
1
,
……
,
�
-
1
}
是第 i 个细胞在时间步 t 的状态； r 指定范围，即给定单元格的任一侧有多少个单元格算作邻居；和
φ
�
通过在中赋值来显式定义
Σ
Σ
到每一个
k
2
r
+
1
（
2
r
+
1
）
�
2
�
+
1
（
2
�
+
1
）
-元组代表所有可能的邻域配置。例如，与
r
=
1
,
Σ
=
{
1
,
0
}
�
=
1
,
Σ
=
{
1
,
0
}
，一个可能的转换规则
φ
�
可以表示如图4（1表示黑色，0表示白色）：
图4
图4
对于给定的单元格，顶部的每个三元组代表 t 处可能的邻域配置，所讨论的单元格是中间的单元格：对于每种配置，底部的正方形指定单元格在 t 处的状态
t
+
1
�
+
1
。这是我们的课堂示例：您将有一个黑色牢房，以防万一其中一个邻居是黑人。
2.2 Wolfram 分类方案
这种简单的表示形式也是广泛采用的 Wolfram 代码 (Wolfram 1983) 的核心，为每个规则分配一个数字：黑色 = 1，白色 = 0，底行可以读取为二进制数 (01011010)；转换为十进制即可得到规则的名称（在本例中为规则 90）。由于 CA 的规则为
r
=
1
�
=
1
和
k
=
2
�
=
2
仅在图的底行有所不同，这种编码方案有效地识别了类中的每个可能的规则。一维 CA
r
=
1
�
=
1
和
k
=
2
�
=
2
是人们可以定义的最简单的 CA 之一，但它们的行为有时非常有趣。当斯蒂芬·沃尔夫勒姆 (Stephen Wolfram) 在八十年代开始探索这个领域时，该课程似乎非常适合。和
r
=
1
�
=
1
，有 8 个可能的邻居（参见上图 4）要映射到
1
,
0
1
,
0
，总共给出
2
8
=
256
2
8
=
256
规则。从随机初始条件开始，Wolfram 继续在许多模拟中观察每个规则的行为。结果，他能够将每条规则的定性行为分类为四个不同类别之一。重复最初的实验，我们模拟了 Wolfram 方案每一类的两个规则的演化。
2.3 256条规则的类别
Class1 规则导致同质状态，所有单元格稳定地以相同的值结束：
规则 250
规则 250
规则 254
规则 254
导致稳定结构或简单周期模式的 2 类规则：
规则 4
规则 4
规则108
规则108
导致看似混乱、非周期性行为的 Class3 规则：
规则 30
规则 30
规则 90
规则 90
Class4 规则导致复杂的模式和结构在点阵中局部传播：
规则 54
规则 54
