细胞自动机，一个模拟细胞间相互影响演化的模型，每个细胞有有限种状态，并按照一定规则相互影响，发生演化。严格定义及数学模型请见维基百科：细胞自动机，Cellular automaton。不过维基里讲的颇为晦涩，在这里我仅就最简的一维细胞自动机谈些自己的看法，尽量讲得严谨易懂。
##初始状态
在最简一维细胞自动机中，每个细胞仅有 0、1 两个状态，所有细胞相邻排列在一个一维空间中。就像下面这样：
1001 0100 0010 0011…
##演化过程
在细胞自动机启动之后，所有细胞（元胞）都会受到相邻细胞（邻元）的影响，按照既定的规则进行演化。
我们先看一张规则表：
| 当前状态 | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
|---|---|---|---|---|---|---|---|---|
| 新状态 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 |
在这张规则表里，第一行用三位二进制数表示元胞和它的左右邻元的当前状态，（若元胞没有左邻元或右邻元，则将缺失邻元的状态记为 0）第二行表示在当前状态下元胞将会演化成什么状态。
举个例子，假设细胞的初始状态为：
1001 1010
首先所有细胞的演化是针对之前的状态同时进行的。对于第一个细胞来说，它没有左邻元，自身状态为 1，右邻元状态为 0，所以经过一次演化后它的状态将变为 1；对于第二个细胞来说，它的左邻元状态为 1，自身状态为 0，右邻元状态为 0，经过一次演化后它的状态将变为 0……
以此类推，我们可以得到经过一次演化后这排细胞的状态：
1011 1110
同理，再经过一次演化后，这排细胞的状态会变成下面这样：
1110 0010
经过多次演化后，我们把每次演化的结果按照时间顺序依次排列，就会得到一个二维矩阵。如下：
1001 1010
1011 1110
1110 0010
1010 0110
1110 1110
1011 1010
我们把 0、1 用黑白格来表示，根据不同的初始状态，会得到各种演化图像：
##Rule 110
对于上面的那张规则表，我们可以用 “01101110” 来表示它（就是表格的第二行），而二进制的 “0110 1110” 在十进制下是 110，因此那张规则表就被称为 Rule 110。同理，从 Rule 0 到 Rule 255，最简一维细胞自动机一共有 256 个可能的规则表。
不同的规则对最后的演化结果有很大的影响，根据照维基的记载，Wolfram 把规则分为四类：
Wolfram, in A New Kind of Science and several papers dating from the mid-1980s, defined four classes into which cellular automata and several other simple computational models can be divided depending on their behavior. While earlier studies in cellular automata tended to try to identify type of patterns for specific rules, Wolfram’s classification was the first attempt to classify the rules themselves. In order of complexity the classes are:
Class 1: Nearly all initial patterns evolve quickly into a stable, homogeneous state. Any randomness in the initial pattern disappears.[32]
Class 2: Nearly all initial patterns evolve quickly into stable or oscillating structures. Some of the randomness in the initial pattern may filter out, but some remains. Local changes to the initial pattern tend to remain local.[32]
Class 3: Nearly all initial patterns evolve in a pseudo-random or chaotic manner. Any stable structures that appear are quickly destroyed by the surrounding noise. Local changes to the initial pattern tend to spread indefinitely.[32]
Class 4: Nearly all initial patterns evolve into structures that interact in complex and interesting ways, with the formation of local structures that are able to survive for long periods of time.[33] Class 2 type stable or oscillating structures may be the eventual outcome, but the number of steps required to reach this state may be very large, even when the initial pattern is relatively simple. Local changes to the initial pattern may spread indefinitely. Wolfram has conjectured that many, if not all class 4 cellular automata are capable of universal computation. This has been proven for Rule 110 and Conway’s game of Life.
这里我比较关注的是第四类规则里的 Rule 110，这个规则在 2000 年就被证明是图灵完备的，可以实现一个最简图灵机并进行通用运算。曾经有人声称用 HTML + CSS3 实现了 Rule 110 自动机并以此来证明 HTML + CSS3 是图灵完备的，在下一篇博客里我将对该例进行探讨。