元胞自动机（二）
规则110
规则110
Class1 包含快速产生统一配置的规则。 Class2 中的规则产生统一的最终模式，或最终模式之间的循环，具体取决于初始配置。尽管可能存在一些规则的模式和结构，但 Class3 成员产生的配置看起来几乎是随机的。
Class4值得特别关注。如果我们观察规则 110 生成的宇宙，我们会看到规则模式（尽管不像规则 108 那样规则）以及一些混沌行为（尽管不像规则 90 那样嘈杂）。现在，CA 执行计算所需的基本特征是其产生“类粒子持久传播模式”的转换规则的能力（Ilachinski 2001：89），即细胞组的局部、稳定但非周期性配置，有时在文献中称为孤子，可以保持其形状。这些配置可以被视为对信息包进行编码，随着时间的推移保存它们，并将它们从一个地方移动到另一个地方：信息可以在时间和空间中传播而不会经历重要的衰减。 Class4 规则行为中的不可预测性也暗示了计算上有趣的特征：根据停止定理（参见图灵机条目中的部分），通用计算的一个关键特征是原则上无法预测给定的计算是否会发生。给定特定输入时停止。这些见解使 Wolfram 推测 Class4 CA 是（唯一的）能够进行通用计算的。直观上，如果我们将 Class4 CA 的初始配置解释为其输入数据，则通用 Class4 CA 可以评估任何有效可计算函数并模拟通用图灵机。正如我们上面提到的，规则 110 确实被证明是计算通用的。
（参见补充文件《256 条规则》。）
2.4 混沌边缘
Class4 规则的中间性质与这样一种想法有关，即有趣的复杂性，例如生物实体及其动力学所表现出的复杂性，位于无聊的规律性和嘈杂的混乱这两个极端之间的中间区域：
也许[生物现象的CA表示]最令人兴奋的含义是生命可能起源于相变附近，而进化反映了生命获得对连续更多影响环境参数的局部控制的过程。它能够将自身维持在秩序与混乱之间的关键平衡点。 （兰顿 1990：13）
CA 不仅提供了直觉，还提供了研究假设的正式框架。八十年代末，“混沌边缘”图片引起了 CA 从业者的极大兴趣。 Packard 1988 和 Langton 1990 是第一个在 CA 背景下对混沌边缘给出现在众所周知的解释的研究。正如米勒和佩奇所说，“这些早期实验表明，处于混沌边缘的系统具有紧急计算的能力”（Miller & Page 2007：129）。这个想法很简单：如果我们采用规则 110 之类的规则并引入一个小扰动，会发生什么？如果我们相信“混沌边缘”假说，我们应该预期通过规则 110 的微小变化获得的规则会表现出简单或混乱的行为。让我们考虑规则 110 的特征映射中从 1 到 0 或 0 到 1 的单个切换。结果是以下八个相邻规则，每个规则与规则 110 相差一位（数组中的对角线，其中的数字为斜体）：
110 111 108 106 102 126 78 46 228
000 0 1 0 0 0 0 0 0 0
001 1 1 0 1 1 1 1 1 1
010 1 1 1 0 1 1 1 1 1
011 1 1 1 1 0 1 1 1 1
100 0 0 0 0 0 1 0 0 0
101 1 1 1 1 1 1 0 1 1
110 1 1 1 1 1 1 1 0 1
111 0 0 0 0 0 0 0 0 1
等级 4 2 2 3 3 3 1 2 1
在第一个近似值中，混沌边缘假设得到证实：八个邻居中的三个是 Class3，三个是 Class2，两个是 Class1：规则 110 是表中唯一的 Class4。为了将这些发现推广到一维 CA 的整个规则类，Langton 引入了一个参数，
λ
�
，这适用于每个
φ
�
： 为了
k
=
2
�
=
2
,
r
=
1
�
=
1
（二元状态，一元范围）CA，
λ
（
φ
）
�
（
�
）
可以计算为转换规则表中映射到非零输出的条目的分数（有关一般定义，请参见 Langton 1990：14）。在我们的例子中，这意味着：
λ
（
φ
）
�
（
�
）
将等于规则列中的个数，例如，
λ
（
φ
）
=
5
/
8
�
（
�
）
=
5
/
8
为了
φ
�
= 规则 110 和
λ
（
φ
）
=
1
/
2
�
（
�
）
=
1
/
2
为了
φ
�
= 规则 46。兰顿的主要发现是一个简单的措施，例如
λ
�
与系统行为相关：如
λ
�
从 0 到 1，系统的平均行为从冻结到周期性模式再到混乱。兰顿挑选 1/2 作为值
λ
�
平均行为首先显示出混乱的证据：规则
φ
�
和
λ
（
φ
）
～
1
/
2
�
（
�
）
～
1
/
2
被强调为处于边缘（参见 Miller & Page 2001：133）。
λ
�
所有规则 混沌规则 复杂规则
0 1 0 0
1/8 8 0 0
1/4 28 2 0
3/8 56 4 1
1/2 70 20 4
5/8 56 4 1
3/4 28 3 0
7/8 8 0 0
1 1 0 0
混沌规则和复杂规则都有一个平均数
λ
�
值约为 1/2，因此显然支持混沌边缘假设。不过，公平地说，有些人对参数的解释作用表示怀疑
λ
�
以及从中得出的推论。尤其是混沌边缘的过渡区域本身就显得很复杂。 Miller 和 Page 指出“存在多个边缘，而不仅仅是一个”（Miller & Page 2007：133）。当我们分析单个规则时，即使是范式规则，总体结果也不成立：
110 111 108 106 102 126 78 46 228
λ
�
5/8 3/4 1/2 1/2 1/2 3/4 1/2 1/2 3/4
如表所示，在规则 110 的邻居中，有一些混乱的规则
φ
�
有
λ
（
φ
）
=
3
/
4
�
（
�
）
=
3
/
4
，一些循环有
λ
（
φ
）
=
1
/
2
�
（
�
）
=
1
/
2
确实，
该空间中被分类为复杂的每一项规则都至少有一个具有较低混沌邻居
λ
�
值和具有更高价值的一个。 （米勒和佩奇 2007 年：135）
Melanie Mitchell、Peter Hraber 和 James Crutchfield 重复了 Langton 和 Packard 的实验，报告了截然不同的结果（Mitchell、Hraber 和 Crutchfield 1994）。特别是，他们报告说，严重的计算现象更接近于混沌
λ
（
φ
）
=
1
/
2
�
（
�
）
=
1
/
2
比之前想象的要多。除了技术点之外，原始研究结果中的一个概念缺陷是聚合统计数据的使用，这在高方差背景下很难解释：
相反，如果假设涉及 CA 规则空间的通用统计属性，即“平均 CA”在给定条件下的“平均”行为
λ
�
——那么“平均行为”的概念必须得到更好的定义。 （米切尔、赫拉伯和克拉奇菲尔德 1994：14）。
虽然可以公平地得出结论，复杂的行为并不处于简单意义上的混沌边缘（即，它与简单的行为并不直接相关）
λ
�
），从那时起，人们对 CA 规则空间中的计算能力和相变之间的联系的兴趣一直在增长。我们将在下面考虑此类发展，特别是在 CA 和计算哲学的背景下。
2.5 更多维度的CA：生命的游戏
尽管一维 CA 的计算意义重大，但哲学问题的讨论仍与二维 CA 相关。第一个 CA 是冯·诺依曼的自我复制自动机，位于二维网格中。此外，二维CA适合表示许多物理、生物甚至人类现象，从完美气体的动力学到暴风雨中鸟类的运动和战场上士兵的运动。最常见的配置是方形或六边形单元，因为它们具有平移和旋转对称性。当然，转向二维也扩展了规则和邻域可能有趣的组合。至于后者，方格网格中最常见的两个选项是冯诺依曼邻域，其中每个单元仅与其四个水平和垂直相邻的单元相互作用，以及摩尔邻域，包括所有八个直接相邻的单元。
作为例子，我们介绍约翰·康威（John Conway）著名的《生命游戏》（或者更简单地说，《生命》）（参见 Berkelamp, Conway, & Guy 1982）。生活很符合我们通常的模式：
正交网格中方形单元的二维晶格。
Σ
=
{
1
,
0
}
Σ
=
{
1
,
0
}
， 所以
|
Σ
|
=
2
|
Σ
|
=
2
（由于我们即将看到的原因，我们可以将 1 表示给定细胞的存活状态，0 表示死亡状态）。
每个单元的邻域由所有八个相邻单元组成（摩尔邻域）。
生命的转变规则如下。在每个时间步 t，细胞可能会发生以下三种情况之一：
出生：如果细胞状态为
t
-
1
�
-
1
为 0（死亡），如果正好有三个邻居为 1（活着），则细胞状态变为 1（活着）
t
-
1
�
-
1
;
生存：如果细胞状态为
t
-
1
�
-
1
为 1（存活），如果两个或三个邻居在此时为 1（存活），则细胞状态仍为 1
t
-
1
�
-
1
;
死亡：如果细胞状态为
t
-
1
�
-
1
为 1（存活），如果少于两个或超过三个邻居为 1（存活），则细胞状态变为 0（死亡）
t
-
1
�
-
1
（细胞可能因“孤独”或“人口过多”而死亡）。
按照 Wolfram 的分类法，生命肯定会被视为 Class4 CA。在这个简单的设置中，即使从非常简单的初始配置开始，周期性结构、稳定块和复杂的移动模式也会出现。康威评论道：
考虑到足够大的生命空间，最初处于随机状态，经过很长一段时间后，智能的、自我繁殖的动物很可能会出现并居住在空间的某些部分。 （引自 Ilachinski 2001：131）
生命爱好者探索了 CA 可能的进化模式，并在所谓的生命动物学中分享了他们的发现（Dennett 2003：41）。这是一个小样本库以及典型模拟的快照（有关更多图片和动画，请参阅最后的其他互联网资源）。滑翔机是基本生命居民中最受欢迎的：一个简单的 5 位结构，滑翔机可以以 4 步周期在生命网格中移动：
滑翔机
滑翔机1
t
0
�
0
滑翔机2
t
1
�
1
滑翔机3
t
12
�
12
蟾蜍是周期 2 闪烁配置：与闪烁器和信标一起，它们是宇宙中最简单的振荡器。
蟾蜍
蟾蜍1
t
0
�
0
蟾蜍2
t
1
�
1
蟾蜍3
t
3
�
3
食者具有吞噬其他结构的特征，例如滑翔机，保持完整的自身形态（因此，它们对生命的计算能力发挥着重要作用）。
吞食滑翔机的食者
食者1
t
0
�
0
食者2
t
2
�
2
食客3
t
4
�
4
从随机初始条件开始的典型生命演化可能包含所有上述值得注意的数字以及更多。即使在几个时间步长之后，一些初始配置也可能最终变成静态或简单的周期性结构。然而，其他配置可以产生非周期性的、日益复杂的环境，其发展可能是不可预测的（即使在我们即将探索的计算意义上也是如此）。正如伊拉钦斯基由此推测的那样：
在观察到生命进化模式看似无限的复杂性和多样性时，几乎不可能不和康威一样想象，如果游戏真的要在无限的格子上进行，那么肯定会出现真正的活的“生命形式” ”，也许它们自己进化成更复杂、可能有感知的“有机体”。 （伊拉钦斯基 2001：133）
生活1
t
0
�
0
生活2
t
10
�
10
生活3
t
20
�
20
生活4
t
30
�
30
生活5
t
40
�
40
生活6
t
175
�
175
关于 CA 的数学文献并不避免使用我们所使用的相同的富有想象力的词汇来描述生命配置：物品诞生、生存、移动、吃掉其他图形、死亡等等。不过，这些模式所居住的宇宙也可以被描述，作为单个细胞的集合，每个细胞并不直接依赖于宏观尺度上发生的事情。而Life上的生命也可以用矩阵和离散序列的简单数学语言来描述。但如果只告诉一个人基本的生命规则，人们很难想象它会产生多么复杂的结果——直到亲眼所见。生命在科学家和哲学家中的声誉可以说来自于它对复杂性、模式形成和现实、持久性和连续性的具有挑战性的天真的直觉：作为我们自己建造的一个玩具宇宙，我们觉得我们应该提前知道什么是动态的。从数学上精确的意义上来说，这已被证明是不可能的。
2.6 通用图灵机的生命
与任何其他 CA 一样，Life 可以被视为一种计算设备：自动机的初始配置可以对输入字符串进行编码。人们可以让系统运行，并在某个时刻读取当前配置作为迄今为止执行的计算的结果，并将其解码为输出字符串。但生命到底能计算什么？事实证明，生命可以计算通用图灵机可以计算的一切，因此，根据图灵的论文，它可以充当通用计算机：适当选择初始条件可以确保系统执行任意算法程序。
Berkelamp、Conway 和 Guy 1982 提出的 Life 通用计算能力的证明在于表明标准数字计算的基本构建块或原语可以通过 Life 生成的适当模式来模拟，特别是： (a) 数据存储或记忆，（b）需要电线和内部时钟的数据传输，以及（c）数据处理，需要一组通用的逻辑门，例如否定，连接和脱节 - 保罗后来在生活中明确实现了实际的图灵机器Rendell（请参阅其他Internet资源）。
这一发现并不重要的是工程学的重要性（没有人会花时间翻译“
24
+
26
/
13
24
+
26
/
13
“进入生活）。但是，它提出了一个概念性问题，即任何宇宙共享生产和托管通用计算机的能力：由于上述停止定理，没有一般算法是决定是否决定是否有一些初始配置为输入，生命最终会消失或停止。从这个意义上讲，自动机的演变是不可预测的。鉴于仅直接数学分析就无法预测计算上普遍存在的CA的发展，因此CA从业者采用了哲学的语言并谈论CA的现象学研究也就不足为奇了（我们将更详细地回到此术语上在下面的第3.4节中，讨论CA如何建模他们可以建模的）。在这里，自动机被实现为计算机软件，并且其进化的可观察到的紧急属性被经验注册为计算机模拟的进步。在Wolfram的短语转过程中，生命在算法上是不可约的：没有算法快捷方式可以预测系统的初始输入。 “与所有计算通用系统一样，生命定义了对自身行为的最有效模拟”（Ilachinski 2001：15）。这就提出了一个重要的哲学问题，即任何能够生产和托管通用计算机的宇宙的可预测性的局限性。
