五、细胞自动机

五、细胞自动机

原文：Chapter 5 Cellular Automatons

译者：飞龙

协议：CC BY-NC-SA 4.0

自豪地采用谷歌翻译

细胞自动机（CA）是一个世界的模型，带有非常简单的物理。 “细胞”的意思是世界被分成一个大口袋，称为细胞。 “自动机”是一台执行计算的机器 - 它可能是一台真机。，但更多时候，“机器”是数学抽象或计算机的模拟。

本章介绍了史蒂文沃尔夫勒姆（Steven Wolfram）在 20 世纪 80 年代进行的实验，表明一些细胞自动机展示出令人惊讶的复杂行为，包括执行任意计算的能力。

我讨论了这些结果的含义，在本章的最后，我提出了在 Python 中高效实现 CA 的方法。

本章的代码位于本书仓库的chap05.ipynb中。使用代码的更多信息，请参见第？章。

5.1 简单的 CA

细胞自动机 [1] 由规则来管理，它决定系统如何即时演化。时间分为离散的步骤，规则规定了，如何根据当前状态计算下一个时间步骤中的世界状态。

automaton（自动机）的复数为 automatons 或 automata。

作为一个微不足道的例子，考虑带有单个细胞的细胞自动机（CA）。细胞状态是用变量xi表示的整数，其中下标i表示xi是时间步骤i期间的系统状态。作为初始条件，x0 = 0。

现在我们需要一个规则。我会任意选择xi = x[i-1] + 1，它表示在每个时间步骤之后，CA 的状态会增加 1。到目前为止，我们有一个简单的 CA ，执行简单的计算：它用于计数。

但是这个 CA 是不合规则的；可能的状态数通常是有限的。为了使其成立，我将选择最小的感兴趣的状态数 2，和另一个简单的规则xi = (x[i-1] + 1) % 2，其中%是余数（或模）运算符。

这个 CA 的行为很简单：闪烁。也就是说，在每个时间步之后，细胞的状态在 0 和 1 之间切换。

大多数 CA 是确定性的，这意味着规则没有任何随机元素；给定相同的初始状态，它们总是产生相同的结果。也有不确定性的 CA，但我不会在这里涉及它们。

5.2 Wolfram 的实验

前一节中的 CA 只有一个细胞，所以我们可以将其视为零维，并且它不是很有趣。在本章的其余部分中，我们将探索一维（1-D）CA，后者会变得非常有趣。

说 CA 有维度就是说细胞被安排在一个连续的空间中，这样它们中的一些可以看作“邻居”。在一维中，有三种自然形式：

有限序列：

数量有限的细胞排成一排。除第一个和最后一个之外的所有细胞都有两个邻居。

环：

数量有限的细胞排列成一个环。所有细胞都有两个邻居。

无限序列：

数量无限的细胞排列成一排。

确定系统如何即时演化的规则，基于“邻域”的概念，即“邻域”，即决定给定细胞的下一个状态的一组细胞。

在二十世纪八十年代初，斯蒂芬沃尔夫勒姆发表了一系列论文，对一维 CA 进行了系统的研究。他确定了四大类行为，每一类都比上一个更有趣。

Wolfram 的实验使用了三个细胞的邻域：细胞本身及其左右邻居。

在这些实验中，这些细胞有两个状态，分别表示为 0 和 1，所以规则可以通过一个表格进行汇总，它将邻域状态（状态的三元组）映射为中心细胞的下一个状态。下表展示了一个示例：

prev	111	110	101	100	011	010	001	000
next	0	0	1	1	0	0	1	0

第一行显示邻居可能拥有的八个状态。第二行显示下一个时间步骤中的中心细胞的状态。作为该表的简明编码，Wolfram 建议将第二行读作二进制数。因为二进制 00110010 是十进制的 50，所以 Wolfram 称这个 CA 为“规则 50”。

图 5.1：十个时间步骤之后的规则 50

上图展示了规则 50 在 10 个时间步骤之后的效果。第一行展示第一个时间步骤内的系统状态; 它起始于一个“开”细胞，其余都是“关”。第二行展示下一个时间步骤中的系统状态，以此类推。

图中的三角形是这些 CA 的典型；这是领域形状的结果吗？在一个时间步骤中，每个细胞都会影响任一方向上的邻居的状态。在下一个时间步骤中，该影响可以在每个方向上向一个细胞传播。因此，过去的每个细胞都有一个“影响三角形”，包括所有可能受其影响的细胞。

5.3 CA 的分类

图 5.2：64 个步骤之后的规则 18

有多少种不同的 CA？

由于每个细胞都处于开或关的状态，我们可以用一位来指定细胞的状态。在三个细胞的邻域中，有 8 种可能的情况，因此规则表中有 8 个条目。由于每个条目都占一个位，我们可以使用 8 位指定一个表。使用 8 位，我们可以指定 256 个不同的规则。

Wolfram 的第一个 CA 实验就是测试所有 256 种可能性并尝试对它们进行分类。

在视觉上检查结果时，他提出 CA 的行为可以分为四类。第一类包含最简单（也是最不感兴趣）的 CA，即从几乎任何起始条件演变为相同统一图案的 CA。作为一个简单的例子，规则 0 总是在一个时间步后产生一个空的图案。

规则 50 是第二类的一个例子。它生成一个带有嵌套结构的简单图案；也就是说，该图案包含许多自身的较小版本。规则 18 使嵌套结构更加清晰；图？显示了 64 步后的样子。

这种模式类似于谢尔宾斯基三角形，你可以在 http://en.wikipedia.org/wiki/Sierpinski_triangle 上阅读。

某些二类 CA 生成的图案复杂而美观，但与第三和第四类相比，它们相对简单。

5.4 随机性

图 5.3：100 个步骤之后的规则 30

第三类包含产生随机性的 CA。规则 30 是一个例子；图？显示 100 个时间步后的样子。

左侧有一个明显的图案，右侧有各种大小的三角形，但中心看起来很随意。事实上，如果你把中间列看做一个比特序列，就很难将其区分于真正的随机序列。它通过了许多统计测试，人们用来测试比特序列是否随机。

产生看起来随机的数字的程序，称为伪随机数字生成器（PRNG）。他们不被认为是真正的随机，因为：

它们中的许多产生规律性序列，可以通过统计来检测。例如，C 标准库中的rand的原始实现，使用了线性同余生成器，生成器生成的序列具有易于检测的序列相关性。
任何使用有限状态（即存储）的 PRNG 最终都会重复。生成器的特点之一就是这种重复周期。
底层过程基本上是确定性的，不同于一些物理过程，如放射性衰减和热噪声，被认为是基本随机的。

现代 PRNG 产生的序列，在统计上与随机值无法区分，并且它们以很长的周期实现，以至于在重复之前宇宙将崩溃。这些发生器的存在，提出了一个问题，即质量好的伪随机序列与由“真正的”随机过程产生的序列之间，是否存在真正差异。在“A New Kind of Science”中，沃尔夫勒姆认为没有（第 315-326 页）。

5.5 确定性

第三类 CA 的存在令人惊讶。为了解释多么令人惊讶，让我从哲学确定性（决定论）开始（参见http://en.wikipedia.org/wiki/Determinism）。许多哲学立场很难准确定义，因为它们有不同的风味。我经常发现，使用从弱到强排列的陈述列表，来定义它们是有用的：

D1：

确定性模型可以对某些物理系统做出准确的预测。

D2：

许多物理系统可以用确定性过程建模，但有些系统本质上是随机的。

D3：

所有事件都是由先验事件造成的，但许多物理系统基本上是不可预测的。

D4：

所有事件都是由先验事件造成的，并且可以（至少原则上）预测。

我构建这个范围的目标是，让 D1 如此弱以至于几乎每个人都会接受它，D4 如此强以至于几乎没有人会接受它，并且有些人会接受中间的陈述。

作为对历史发展和科学发现的回应，世界舆论的质心沿着这个范围摆动。在科学革命之前，许多人认为宇宙的运作基本上是不可预测的，或由超自然力量所控制。在牛顿力学的胜利之后，一些乐观主义者开始相信像 D4 这样的东西；例如，皮埃尔-西蒙拉普拉斯（Pierre-Simon Laplace）在 1814 年写道：

我们可以把宇宙的现状看作过去的果和未来的因。一个智能在某个特定的时刻，知道所有使自然运动的力量，以及构成自然的所有物品的所有位置，如果它也足够大，来提交这些数据用于分析，它会将宇宙最大的天体和最小的原子的运动汇总成一个公式；对于这样的智能来说，没有什么是不确定的，未来就像过去一样会存在于它的眼前。

这种“智能”被称为“拉普拉斯的恶魔”。见 http://en.wikipedia.org/wiki/Laplace's_demon。在这种情况下，“恶魔”这个词具有“精神”的意义，没有邪恶的含义。

19 世纪和 20 世纪的发现逐渐打破了拉普拉斯的希望。热力学，放射性和量子力学对强式的决定论构成了连续的挑战。

在 20 世纪 60 年代，混沌理论表明，在某些确定性系统中，预测只能在短时间尺度上进行，并受初始条件测量精度的限制。

大多数这些系统，是空间连续（不是时间）和非线性的，所以它们行为的复杂性并不令人惊讶。沃尔夫勒姆在简单的细胞自动机中展示的复杂行为更令人惊讶，并且令人不安，至少对于确定性的世界观来说。

到目前为止，我一直关注对确定性的科学挑战，但是最持久的反对意见是确定性与人类自由意志之间的冲突。复杂性科学为这种明显的冲突提供了可能的解决方案; 我将在第？章中回到这个话题。

5.6 飞船

图 5.4：100 步之后的规则 110

第四类 CA 的行为更令人惊讶。几个一维 CA，最着名的是规则 110，是图灵完备的，这意味着他们可以计算任何可计算的函数。这个属性也称为普遍性，由 Matthew Cook 在 1998 年证明。请参阅 http://en.wikipedia.org/wiki/Rule_110。

图？展示了初始条件为单个细胞和 100 个时间步骤的规则 110 的样子。在这个时间尺度上，没有发生什么特别的事情。有一些有规律的模式，但也有一些难以表述的特征。

图？展示了更大的图像，它起始于一个随机的初始条件和 600 个时间步骤：

图 5.5：初始条件随机和 600 个时间步骤的规则 110

经过大约 100 个步骤后，背景变成了简单的重复模式，但背景中有一些持久性结构表现为干扰。其中一些结构是稳定的，所以它们表现为垂直线条。其他的在空间中平移，表现为不同斜率的对角线，取决于它们移动一列所需的时间步数。这些结构被称为飞船。

飞船之间的碰撞产生不同的结果，取决于飞船的类型和它们碰撞时的阶段。一些碰撞歼灭两艘船，其他船只保持不变；还有一些产生不同类型的一艘或多艘船只。

这些碰撞是 CA 规则 110 中的计算基础。如果你将飞船视为通过电线传播的信号，并将碰撞视为计算 AND 和 OR 等逻辑运算的门，那么你可以看到 CA 执行计算的意义。

5.7 通用性

为了理解通用性，我们必须理解可计算性理论，它关于计算模型和计算的东西。

最通用的计算模型之一是图灵机，它是由艾伦图灵在 1936 年提出的一种抽象计算机。图灵机是一个一维 CA，两个方向上都是无限的，并增加了一个读写头。在任何时候，头部都位于一个细胞上。它可以读取该细胞的状态（通常只有两种状态），并可以将新值写入细胞中。

此外，该机器还有一个寄存器，用于记录机器的状态（有限数量的状态之一）和一张规则表。对于每个机器状态和细胞状态，表格规定一个操作。操作包括修改头部所在的细胞，并向左或向右移动一个细胞。

图灵机并不是计算机的实际设计，但它模拟了常见的计算机体系结构。对于在真实计算机上运行的给定程序，（至少原则上）可以构造一个执行等效计算的图灵机。

图灵机很有用，因为它可以刻画一组图灵机可以计算的函数，这就是图灵所做的事情。这个集合中的函数被称为图灵可计算的。

说图灵机可以计算任何图灵可计算函数，是一个赘述：根据定义它是真的。但图灵可计算性比这更有趣。

事实证明，任何人提出的每个合理的计算模型都是图灵完备的；也就是说，它可以计算与图灵机完全相同的一组函数。其中一些模型，如 lamdba 演算，与图灵机非常不同，所以它们的等价性令人惊讶。

这种观察产生了丘奇-图灵理论，它基本上定义了可计算的含义。这个“理论”是，图灵可计算性是可计算性的正确，或至少是自然定义，因为它描述了这种计算模型的多样化集合的威力。

CA 规则 110是另一种计算模型，其简单性非常出色。它也是通用的，为丘奇-图灵理论提供了支持。

在“A New Kind of Science”中，沃尔夫勒姆阐述了这个理论的一个变种，他称之为“计算等价性原理”：

几乎所有不明显的简单过程，都可以看作是具有复杂性相同的计算。
更具体来说，计算等价性原理表明，在自然界中发现的系统可以执行达到最高（“通用”）级别的计算能力的计算，并且大多数系统实际上实现了这种最高级别的计算能力。因此，大多数系统在计算上是等效的（参见 http://mathworld.wolfram.com/PrincipleofComputationalEquivalence.html）。

将这些定义应用于 CA，第一类和第二类“显然很简单”。第三类可能不那么明显，但在某种程度上，完美的随机性就像完美的顺序一样简单；复杂性存在于中间。所以 Wolfram 声称第四类行为在自然界中很常见，并且几乎所有表现它的系统在计算上都是等价的。

5.8 可证伪性

沃尔夫勒姆认为，他的原则比丘奇图灵理论更强大，因为它是关于自然界的，而不是抽象的计算模型。但是说自然过程“可以看作计算”，使我觉得像理论选择的陈述。而不仅仅是自然世界的假设。

此外，对于像“几乎”和“明显简单”这样的未定义术语的资格，他的假设可能是不可证伪的。可证伪性是科学哲学的一个观点，由卡尔波普尔（Karl Popper）提出，作为科学假说与伪科学之间的界限。如果一个假设是假的，并且有一个实验，至少在实用性领域，它能反驳这个假设，那么这个假设是可证伪的。

例如，地球上的所有生命都来自共同祖先的说法是可证伪的，因为它对现代物种（在其他东西中）的基因相似性做出了特定的预测。如果我们发现了一种新物种，它的 DNA 与我们的 DNA 几乎完全不同，那么这就反驳了共同血统理论（或者至少引起质疑）。

另一方面，所谓“神创论”，即所有物种都是由超自然力量创造出来的，是不可证实的，因为没有任何我们可以观察到的，与自然世界相矛盾的东西。任何实验的结果都可以归因于创作者的意志。

不可证伪的假设可能有吸引力，因为不可能反驳它们。如果你的目标是永远不会被证明是错误的，你应该尽可能选择不可证伪的假设。

但是，如果你的目标是对世界做出可靠的预测 - 而这至少是科学的目标之一 - 那么不可证伪的假设是无用的。问题是他们没有结果（如果他们有结果，他们将是可证伪的）。

例如，如果神创论是真实的，那我知道它有什么好处呢？它不会告诉我任何造物主的事情，除了他有一种“对甲虫的非常喜爱”（归因于 J. B. S. Haldane）。不同于共同血统理论，它通告许多科学和生物工程领域，理解这个世界或者为之行动是没有用的。

5.9 这是什么模型？

图 5.6：一个简单物理模型的逻辑结构

一些细胞自动机主要是数学工艺品。它们很有趣，因为它们令人惊讶，或者有用，或者漂亮，或者因为它们提供了创建新式数学的工具（比如丘奇图灵定理）。

但是，它们是不是物理系统的模型还并不清楚。如果他们是，他们是高度抽象的，也就是说他们并不很详细或现实。

例如，某些锥螺物种在它们的壳上产生图案，类似于由细胞自动机产生的图案（参见en.wikipedia.org/wiki/Cone_snail）。所以假设 CA 是随着壳长大而在壳上产生图案的机制的模型，这是很自然的。但是，至少在最初阶段，模型元素（所谓的细胞，邻居之间的通信，规则）如何对应成长的蜗牛（真实细胞，化学信号，蛋白质交互网络）的元素，还并不清楚。

对于传统的物理模型，现实是一种优点。如果模型的元素对应物理系统的元素，则模型和系统之间有明显的类比。总的来说，我们期望更现实的模型能够做出更好的预测，并提供更可信的解释。

当然，这只是一个事实。更详细的模型更难以处理，并且通常不太适合分析。在某些时候，模型变得如此复杂，以至于直接对系统进行实验更容易。

在另一个极端，简单的模型可以完全引人注目，因为它们很简单。

简单模型提供了与详细模型不同的解释。使用详细的模型，论述就像这样：“我们对物理系统S感兴趣，所以我们构造了一个详细模型M，并且通过分析和模拟表明M表现出一种行为B，它与实际系统的观察O（定性或定量地）相似。那么为什么O会发生？因为S类似于M，而B类似于O，我们可以证明M导致B。”

使用简单的模型，我们不能说S与M相似，因为它不是。相反，论述是这样的：“有一组模型共享一组共同的特征。任何具有这些特征的模型都表现出行为B。如果我们进行类似于B的观察O，解释它的一种方式是，这表明系统S具有足以产生1的一组特征。”

对于这种说法，增加更多的特征并没有帮助。使模型更真实不会使模型更可靠；它只掩盖了导致O的基本特征，和S特有的附带特征之间的差异。

图？显示了这种模型的逻辑结构。特征x和y足以产生行为。增加更多细节，如特征w和z，可能会使模型更加逼真，但是这种现实并没有增加解释力。

5.10 CA 的实现

图 5.7：列表的列表（左）和 NumPy 数组（右）

为了生成本章中的图形，我编写了一个名为 CA 的 Python 类，它代表细胞自动机，以及用于绘制结果的类。在接下来的几节中，我会解释他们如何工作。

为了存储 CA 的状态，我使用了 NumPy 数组，这是一个多维数据结构，其元素类型都相同。它与嵌套列表类似，但通常更小更快。图？说明了原因。左侧的图展示了整数列表的列表；每个点表示一个引用，它占用 4-8 个字节。要访问其中的一个整数，你必须跟随两个引用。

右图显示了相同整数的数组。因为这些元素大小都相同，所以它们可以连续存储在内存中。这种安排节省了空间，因为它不使用引用，并且节省了时间，因为可以直接从下标计算元素的位置；没有必要跟随一系列的引用。

为了解释我的代码如何工作，我将以一个 CA 开始，它计算每个邻域中细胞的“奇偶性”。如果数字是偶数，则数字的奇偶性为 0；如果数字为奇数，则奇偶性为 1。

首先，我在第一行的中间，创建带有单个 1 的零数组。

>>> rows = 5
>>> cols = 11
>>> ca = np.zeros((rows, cols))
>>> ca[0, 5] = 1
print(ca)
[[ 0.  0.  0.  0.  0.  1.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]]

plot_ca用图形展示了结果。

mport matplotlib.pyplot as plt
def plot_ca(ca, rows, cols):
    cmap = plt.get_cmap('Blues')
    plt.imshow(array, interpolation='none', cmap=cmap)

按照约定，我使用缩写名称plt引入了pyplot。 imshow将数组视为“图像”并显示它。使用颜色表'Blues'，将“开”细胞绘制为深蓝色，“关”细胞绘制为淡蓝色。

现在，为了计算下一个时间步中的 CA 状态，我们可以使用step：


def step(array, i):
    rows, cols = array.shape
    for j in range(1, cols):
        array[i, j] = sum(array[i-1, j-1:j+2]) % 2

参数ca是表示 CA 状态的 NumPy 数组。 rows和col是数组的维数，而i是我们应该计算的时间步骤的索引。我用i来表示数组的行，它们对应于时间，j表示对应于空间的列。

在step内部，我们遍历第i行的元素。每个元素是来自上一行的三个元素的总和，并对 2 取余。

5.11 互相关

上一节中的step函数很简单，但速度并不是很快。一般来说，如果我们用 NumPy 操作替换循环，我们可以加速这样的操作，因为 Python 解释器中的for循环会产生大量开销。在本节中，我将展示如何使用NumPy函数相关来加快步骤。

首先，我们可以使用数组乘法来代替切片运算符来选择邻域。具体来说，我们将数组乘以一个窗口，其中我们想要选择的细胞为一，其余为零。

例如，以下窗口选择前三个元素：


>>> window = np.zeros(cols, dtype=np.int8)
>>> window[:3] = 1
>>> print(window)
[1 1 1 0 0 0 0 0 0 0 0]

如果我们乘以数组的最后一行，我们会得到前三个元素：

>>> print(array[4])
>>> print(window * array[4])
[0 1 0 0 0 1 0 0 0 1 0]
[0 1 0 0 0 0 0 0 0 0 0]

现在我们可以使用sum和模运算符来计算下一行的第一个元素：


>>> sum(window * array[4]) % 2
1

如果我们将窗口向右移动，它会选择接下来的三个元素，以此类推。所以我们可以像这样重写step：


def step2(array, i):
    rows, cols = array.shape
    window = np.zeros(cols)
    window[:3] = 1
    for j in range(1, cols):
        array[i, j] = sum(window * array[i-1]) % 2
        window = np.roll(window, 1)

roll将窗口向右移动（它也把末尾的补在开头，但不影响这个函数）。

step2产生step的相同结果。它仍然不是非常快，但是它朝着正确的方向迈出了一步，因为我们刚刚执行的操作（乘以窗口，将结果相加，移动窗口并重复）用于各种应用。它被称为互相关，而 NumPy 提供了一个称为correlate的函数来计算它。

我们可以用它来编写更快，更简单的步骤：


def step3(array, i):
    window = np.array([1, 1, 1])
    array[i] = np.correlate(array[i-1], window, mode='same') % 2

当我们使用np.correlate时，窗口不必与数组大小相同，因此使窗口更简单一些。

mode参数决定结果的大小。你可以阅读 NumPy 文档中的详细信息，但是当模式为'same'时，结果与输入大小相同。

5.12 CA 表

现在还差一步。如果 CA 规则仅取决于邻居的总和，那么我们迄今为止的函数仍然有效，但大多数规则还取决于哪些邻居是开或者关的。例如，100 和 001 可能会产生不同的结果。

我们可以使用一个包含元素[4,2,1]的窗口，使step更加通用，它将邻域解释为一个二进制数。例如，邻域 100 产生 4；010 产生 2，001 产生 1。然后我们可以在规则表中查找这些结果。

以下是更一般的步骤：


def step4(array, i):
    window = np.array([4, 2, 1])
    corr = np.correlate(array[i-1], window, mode='same')
    array[i] = table[corr]

前两行几乎相同。最后一行在table中查找corr的每个元素，并将结果赋给array[i]。

最后，这是计算表的函数：


def make_table(rule):
    rule = np.array([rule], dtype=np.uint8)
    table = np.unpackbits(rule)[::-1]
    return table

参数rule是一个 0 到 255 的整数。第一行将规则放入单个元素的数组中，以便我们可以使用unpackbits，将规则编号转换为其二进制表示形式。例如，以下是规则 150 的表：


>>> table = make_table(150)
>>> print(table)
[0 1 1 0 1 0 0 1]

在thinkcomplexity.py中，你将找到CA的定义，它封装了本节中的代码，以及两个绘制 CA 的类，PyplotDrawer和EPSDrawer。

5.13 练习

练习 1

本章的代码位于本书仓库的 Jupyter 笔记本chap05.ipynb中。打开这个笔记本，阅读代码，然后运行单元格。你可以使用这个笔记本来做本章的练习。我的解决方案在chap05soln.ipynb中。

练习 2

这个练习要求你试验规则 110 以及它的一些飞船。

阅读规则 110 的维基百科页面，其中描述了其背景图案和飞船：https://en.wikipedia.org/wiki/Rule_110。
使用产生稳定背景图案的初始条件创建 CA 规则 110。

请注意，CA 类提供了start_string，它允许你使用 1 和 0 的字符串初始化数组的状态。
通过在行的中心添加不同的图案来修改初始条件，并查看哪些产生了飞船。对于一些n的合理的值，你可能想列举所有可能的n位图案。对于每个飞船，你能找到平移的时间和速度吗？你能找到的最大的飞船是什么？
当宇宙飞船相撞时会发生什么？

练习 3

这个练习的目标是实现一个图灵机。

阅读 http://en.wikipedia.org/wiki/Turing_machine 来了解图灵机。
编写一个名为Turing的类来实现图灵机。对于动作表，使用三个状态的 Busy Beaver 的规则。
写一个名为TuringDrawer的类，该类生成一个图像，表示磁带状态以及磁头位置和状态。可能的外观的一个示例，请参阅 http://mathworld.wolfram.com/TuringMachine.html。

练习 4

本练习要求你执行并测试几个 PRNG。为了进行测试，你需要安装 DieHarder，你可以从 https://www.phy.duke.edu/~rgb/General/dieharder.php 下载 DieHarder，也可能为你的操作系统作为软件包提供。
编写一个程序，实现 http://en.wikipedia.org/wiki/Linear_congruential_generator 中描述的线性同余生成器之一。使用 DieHarder 进行测试。
阅读 Pythonrandom模块的文档。它使用了什么 PRNG？测试它。
使用几百个细胞实现 CA 规则 30，在合理的时间内以尽可能多的时间步骤运行它，然后将中心列输出为位序列。测试它。

练习 5

可证伪性是一个吸引人的和有用的想法，但在科学哲学家中，它并不普遍视为界限的解决方案，正如波普尔所声称的那样。

阅读 http://en.wikipedia.org/wiki/Fififiability 并回答以下问题。

界限问题是什么？
根据波普尔的说法，可证伪性是否解决了界限问题？
给出两个理论示例，一个被认为是科学，另一个被认为是非科学，它们由可证伪性的标准成功地区分开。
你能总结出科学哲学家和历史学家对波普尔的主张提出的，一个或多个反对意见吗？
你是否有这样的感觉，即实践哲学家对波普尔的工作给予高度评价？