模式随处可见。从艺术到数学，从音乐到生物学，模式几乎涵盖了我们生活和文化的方方面面。这并非巧合，因为人类的思想在模式的创造和认识方面表现出色。Cellular Automata由Stephen Wolfram博士（Mathematica和Wolfram Alpha的创建者）推广，元胞自动机（CA）是由一组定义明确的规则生成的模式，但能够表现出复杂的，有时甚至是随机的行为。
起初，我看到这些模式只是看起来有趣的图像。CA不仅仅能产生漂亮的图片,还提供了对许多类型的复杂系统进行建模的方法，而这一事实本身可能对AI的未来以及包括区块链在内的许多其他类型的技术产生重大影响。
这篇文章是关于CA及其应用的思考和实验的大杂烩，所以在阅读了这些模式的以下介绍之后，以及关于Rule 30的一些内容。
1.背景：什么是元胞自动机？
元胞自动机的一个简单示例是根据一组生成模式的规则随时间演变的cells网格（http://mathworld.wolfram.com/CellularAutomaton.html）。以下是“Rule 1”创建的CA的简单示例：
Cellular Automaton Generated by Rule 1
在第一行，我们从一排白色cells开始，中间有一个黑色cell。这是我们的初始条件。我们可以提出各种各样的起始条件，但现在让我们保持简单。为了生成后续行，我们应用一个简单的规则：对于我们生成的行中的每个cell，查看它上面的三个cells（即左上角，顶部中间和右上角）。如果所有三个都是白色的，那么当前的单元格应该是黑色的。否则，下一个单元格应为白色。也许可以通过图形更好地理解这条规则：
Rule 1
每个方形窗口中的前三个cells包含我们可能在包含三个cells的子行中观察到的可能模式。如果我们找到那个模式，我们直接在三个下面绘制相应的单元格。
我们可以继续按照我们的意愿为后续行应用此规则。这个CA包含一个明显的模式，并不是太有趣，但还有许多其他规则供我们探索！实际上，由于binary cells依赖于它上面的三个binary cells，因此在该系统中有2 ^（2³）=2⁸= 256个规则。
一个稍微有趣的CA是“Rule 50”：
Cellular Automaton Generated by Rule 50
Rule 50
虽然稍微复杂一些，但Rule 50仍然包含一种无聊，可预测的模式。让我们看看几个例子，看看其他CA有哪些能力：
Cellular Automaton Generated by Rule 54
Cellular Automaton Generated by Rule 62
Cellular Automaton Generated by Rule 90
Rule 90
Rule 90非常吸引人。注意它的递归结构 - 整个模式类似于一个三角形，但是这个结构可以分解成更小但相似的三角形。现在，这些较小的三角形可以分解成更小的三角形，依此类推，直到我们到达一个无法进一步分割的cell。令我感到惊讶的是，这样一个简单的生成规则可以创造出如此美丽的模式。然而Rule 90仍然是可预测的，因为如果我们继续根据生成规则生成越来越多的行，我们就能很清楚模式会是什么样子。但是所有CA都可以预测吗？
令人惊讶的是，答案是否定的。
2.Rule 30的不合理随机性
Cellular Automaton Generated by Rule 30
Rule 30
注意CA图中的两种不同行为 - 而左侧看似相当有序，右侧看起来很混乱！由于似乎没有任何明确的模式，接下来的几行看起来很明显。事实上，数学家表明，这种结构符合许多严格的伪随机性测试（数学随机性，而不是在自然界观察到的真实随机性）。这种伪随机性是如此强大，以至于Wolfram的计算语言Mathematica使用Rule 30作为其随机数生成器！
真正令人着迷的是这种混乱是如何从一个简单的起始条件和一套简单的规则中产生的。这可能会提醒一种“蝴蝶效应”，这是一种假设现象，其中蝴蝶拍打它的翅膀，从而引起空气中的轻微干扰，这会引起微风的干扰，从而导致风模式的干扰，这会导致飓风。这个事件虽然相当荒谬，但在自然界中无疑是可以想象的。Rule 30的有趣之处在于它发生在计算世界中，即程序世界。
浅谈计算机程序的行为
计算机程序本质上是为机器编写的一组清晰，明确的指令。程序员编写指令并为机器提供输入数据。机器通过操纵电路执行输入指令，并返回计算结果。机器虽然在当今世界是数字的，但最终是机械设备，它们将数字加在一起并在存储器中移动这些数字。因此，我们希望机器的运行与我们告诉他们完全相同。如果我们告诉机器计算2 + 2，我们希望答案为4，如果我们告诉它删除存储在内存中特定位置的数字，那么我们就是这么想的。如果不是这样，机器将不会非常有用！重点是，机器做我们告诉他们要做的事情，仅此而已。
CA实际上是程序：它们具有输入（cells的起始行），用于操纵输入的一组规则，并且它们具有输出（观察到的模式）。但就CA而言，我们真的知道我们告诉他们的是什么吗？我们已经看到了简单的CA程序如何表现出复杂，不可预测的行为。即使程序完全按照我们的要求执行，我们也不知道输出是什么。从某种意义上说，这个程序已经脱离了我们的理解。
虽然大多数CA表现出可预测的行为，但我们对Rule 30的行为的直觉完全崩溃了。上图模式的下一行可能是什么？了解模式的下一部分的唯一方法是计算它。这引导我们进行下一次讨论，即计算不可约性。
3.计算不可约性和区块链
对于那些仍然对这个流行词的含义感到好奇的人来说，Blockchain只是计算机之间的信任系统。该信托的应用范围从金融交易到安全投票系统。为了在任何两方之间存在信任，必须首先确定某种基础。黄金支持金融交易和货币，情绪稳定在人与人之间建立信任，数学知识使我们信任计算机程序的正确性。在区块链中，通过以安全的方式将信息块链接在一起来创建信任，因此得名。
简单讨论量子计算机如何打破区块链
在过去的几年里，大多数情况下都是理论上的练习，但是像IBM这样的几家公司现在正在开发基本的量子计算机。这种即将到来的技术可能会彻底破坏质数分解，从而给世界密码系统带来压力。量子计算机的内部工作原理超出了本文的范围，但我们的想法是,他们可以利用量子力学和各种属性的素数执行某些类型的计算,包括质因数分解,指数增长速度比经典计算机。当这些类型的机器变得普遍时，许多现代的POW问题可能会失去它们的有效性。我们应该注意到，并不是所有的问题都能被量子计算机更有效地解决。到目前为止，数学家们只知道少数几个问题可以通过量子物理和数字理论之间的特殊关系来加速，这些关系可以创建计算捷径。当在量子机器上运行时，许多问题都不能加速。
元胞自动机为工作问题提供了一个潜在的证据，它可能不那么容易受到量子革命的影响。我们之前讨论过一些CAs(即Rule 30)如何具有这样的质量，即没有快捷方式来确定模式的行为——确定模式中的下一行的唯一方法是实际花费时间来计算它。这种没有计算快捷方式的属性被恰当地称为计算不可约性。CA模式中的每一行必须按顺序计算，每一行的计算依赖于前一行计算的完成。因此，CAs需要花费大量的时间来执行计算，这使它们成为工作问题的有力证据。
我提出的一个问题可以用于这种机制:给定来自CA模式的第n行，什么规则/初始条件组合可以创建它?
某些CA的第n行的可能示例
假设上图是某些CA模式的第100行。那么问题是回溯创建该行的未知计算。解决这个问题听起来很难！想象一下必须考虑的所有可能的规则和初始条件。但是，一旦问题得到解决，并且我们知道在第100行生成此特定模式的规则和起始条件，验证解决方案非常简单。我们只是采用起始条件并应用规则来生成后续行，然后确保最后一行与我们在问题陈述中提供的行相同。
计算困难，容易验证，计算上不可约，涉及元胞自动机的计算可能提供必要的机制，以确保区块链在整个量子时代的完整性。
4.元胞自动机和神经网络实验
我们之前已经讨论过在Rule 30中预测模式的难度，至少在抽象层面上是如此。人类的直觉无法预测Rule 30中看不见的行序列，但计算机在这方面的表现如何呢？为了回答这个问题，我进行了一系列涉及神经网络的实验。我尝试创建一个简单的前馈网络，以预测给定前一行的CA模式中的下一行。换句话说，神经网络的目标是发现管理几种CA模式创建的潜规则。
对于那些有深度学习经验的人，我展示了我用于下面所有实验的网络架构。我使用了具有1000个神经元的3个隐藏层，具有LeakyReLU激活，ADAM优化和sigmoid 输出层。为了阻止过度拟合，我包括了几个dropout层。
输入是n×m矩阵X，其包含n个CA行的示例，每行具有m个单元，并且输出是包含n个CA行的矩阵y，其直接对应于X中的那些CA行之后的CA行。
# data contains observed rows from the automata pattern
X = np.array(data[0:-2])
y = np.array(data[1:-1]) # offset by 1
X_train, X_test, y_train, y_test = train_test_split(X,
y, train_size=0.8)
model = Sequential()
model.add(Dense(1000, activation="linear", input_dim = X_train.shape[1]))
model.add(LeakyReLU())
model.add(Dense(1000, activation="linear") )
model.add(LeakyReLU())
model.add(Dropout(0.5))
model.add(Dense(1000, activation="linear") )
model.add(LeakyReLU())
model.add(Dense(1000, activation="linear") )
model.add(LeakyReLU())
model.add(Dropout(0.5))
model.add(Dense(y.shape[1], activation="sigmoid") )
optim = keras.optimizers.Adam(lr=0.0001)
model.compile(loss='mse',
optimizer=optim )
history = model.fit(X_train, y_train, validation_split=0.2, epochs=100)
对于第一个实验，我使用简单的Rule 1生成行。下面是测试数据的ROC曲线。
在某种意义上，该模型似乎正确地确定了Rule 1的生成机制。也就是说，给定一行单元格，神经网络能够像Rule 1那样计算下一行。让我们尝试一个最复杂的例子，比如Rule 54
同样，神经网络在这里做得很好。蓝色线条在左上方略微圆润，表明性能不佳，但仍然相当不错。现在让我们预测一个我最喜欢的CA的行，Rule 90（回想一下这个CA的模式包含一个有趣的递归结构）。
神经网络做得很糟糕。请记住，Rule 90只是生成模式的函数，而且非常简单。从ROC曲线看，网络似乎正在进行随机猜测。一个人可以看两个连续的行，并且有一点工作推断出所使用的模式。然而，神经网络似乎在这项任务中失败了。为了更好地衡量，让我们看看当我们使用Rule 30时会发生什么。
在这种情况下，网络在大多数情况下都倾向于做出积极的预测。虽然ROC曲线表明Rule 30具有更好的预测能力，但这并不是说Rule 30很容易预测，而是说管理这个CA的规则比使用Rule 90的实验更容易确定。
我在实验中观察到的一个有趣现象是测试损失曲线。在所有实验中，除了Rule 30，损失收敛。然而，在Rule 30情况下，随着更多的训练，损失开始增加。这通常表明模型过拟合。我不知道Rule 30规则的混乱和这种不收敛之间是否有联系，但这很有趣。
这是各种实验的测试损失曲线。
5.元胞自动机和人工智能的未来
由于元胞自动机是图灵完成的，它们能够计算任何可以计算和建模几乎任何类型系统的东西。他们有一天会被用来模拟智力吗?过去对智能建模的尝试，以及人们可能认为人工神经网络的尝试，都遇到了同样的问题:我们并不真正知道什么是智能。然而，这可能不是必要的。我们之前讨论过程序如何显示行为，在某种意义上，超越了程序员的意图。理解程序的行为在其创建过程中并不重要。此外，程序的行为会随着时间的推移而改变和适应，产生混乱和随机性。也许有一天，我们将创造一个CA，它以一种进化的方式进化，最终成为智能的模型。当然，这可能涉及到更先进的CAs，它们不需要在简单的黑白网格上操作，但这并不意味着这些系统可能包含把人工智能提升到下一个级别的能力。
閱讀更多 不靠譜的貓 的文章
