自动机 | 林德熙

今天分享的是细胞自动机，细胞自动机是一个学科，我今天要讲的是狭义的细胞自动机，广义的细胞自动机的边界还是模糊的。可能大家会把细胞自动机和dna编程混淆，实际上他们是有交集的，但是不同的两个学科，交集就是分形，自然界中处处存在分形。

我说的内容有一点的哲学，但是不需要进入深入思考，有段时间我差点想疯了。

一开始先让大家看一个图。

在说到自动机之前，来说下现在世界的两个 Bug ，一个是递归，一个是自动机。

递归是大家熟悉的，图灵机模型就是递归模型。

大概说下图灵机，图灵机，就是假设有一张无限长的字条，字条有固定长度的格子，人只能一次读一个格子，格子写着符号，人可以改写他现在读的格子的符号，根据他读到的符号或读过的，决定他下一个要读的格子。

为什么说递归是一个 Bug ，原因：他可以证明没有万能的上帝，可以证明现在的世界是假的。

假设存在万能的上帝，于是让上帝做出他吃不下的饭，上帝是万能的。上帝做出他吃不下的饭。

进入递归，世界上不存在上帝吃不下的饭，上帝是万能的，我做的饭他是可以吃下去的。

于是上帝做不出他吃不下的饭，所以没有上帝。

这是罗尔悖论，递归做出的悖论。

可能很多人玩过我的世界，有大神在我的世界弄出了电脑，于是在我的世界弄出的电脑里面玩我的世界……

有人做出来一个可以在电脑模拟的世界，于是这个世界发展到一定时候，他们的人类造出了电脑，过了好久，他们可以用电脑模拟世界，于是过了好久，虚拟的世界出现了人类，过了好久，他们做出计算机……

根据上面说的，现在的世界处于现实世界的概率是 0 也就是当前所在的世界就是虚拟的世界

自动机如何也是一个 Bug ，因为他是一个问题，世界如何做出来的。

首先来说下历史，这个自动机的提出是在 1940 年，祖师爷冯诺依曼提出的，他是为了解决人工智能的问题而提出的。因为我前段时间在做人工智能，所以对他有一些了解。现在世界上的计算机用的都是冯诺依曼体系，现在影响了世界差不多一个世纪，自动机，是现在才有比较好的发展，可能以后会继续影响世界。

自动机使用的思想：采用局相互作用规则，最终产生整体的自复制构型。

用程序员的话是：1. 首先有固定维度的空间，空间有固定大小的格子，每个格子有一个 Cell 。

每个 Cell 有自己的状态，状态的值是有限的。
每个时刻， Cell 都检查他的邻居的状态，并且根据邻居的状态，改变自己下一时刻的状态。他的邻居是包括他的自己。

于是他的序列是不可控的，当你想知道他的第 n 个状态时，你需要计算他第 n-1 个状态，而想要知道 n-1 个状态是什么，就需要计算 n-2 个状态是什么才可以。在复杂的规则下，人类是很难求出一条公式可以表示输入 n 拿到状态，只能通过持续的计算，才能计算出第 n 个状态。在空间足够大的时候，同时 n 也足够大，这个计算量将会特别可怕。就像神兽[拉普拉斯妖(https://zhuanlan.zhihu.com/p/35239781 )知道了当前宇宙所有粒子的状态，但是因为计算量太大，在这个宇宙内的计算机很难计算出这个宇宙的下一次粒子的状态，或计算的时间长于现实粒子状态修改的时间。也就是即使你知道当前宇宙的所有粒子的状态，你在当前宇宙里面，你有一个强力的计算机，但是这个计算机的计算能力够不够强可以计算出所有粒子的下一个状态是一个问题，从当前状态计算出下一次状态的时间也是问题，例如当前宇宙的所有粒子的更改时间是 0.1 秒，但是你的计算时间需要 1 秒，同时你也没有任何数学公式可以直接输入一个时间就计算出所有粒子的状态，你只能一步步计算，那么你也无法预测这个宇宙

如果简单一点，通过这个规则构建一个简单的时间，一个简单的世界，可以由几个简单规则组成。

现在的世界也是由简单的规则做的，但是在这个世界的渣渣是很难知道这个世界的简单规则，反而会提出很多复杂的规则

开始做一个世界，这个世界有三条规则。