简短程序能产生大的复杂性吗？

对逻辑运算的数学分析揭示了确定性计算能做什么和不能做什么的基本限制。以下3条原理很重要：

原理1：简单输入和简单变换规则能（但并不必然）导致输出具有大的复杂性。

原理2：如果简单变换规则作用于简单输入产生大的复杂性，则变换需要很多计算步骤。

原理3：许多复杂对象的形成需要复杂的程序。这类对象无法通过简单规则作用于简单输入产生，无论多少计算步骤也不行。

沃尔弗拉姆深入研究了原理1，并在《新科学》一书中展示了他的许多发现。他将NKS（新科学）系统定义为通过简单规则和输入产生大的复杂性的逻辑系统，并认为我们在物理世界中观察到的大部分复杂性都是原理1的体现。

图2.3到图2.6展示了4个NKS系统。这些例子被称为元胞自动机（CA），其状态是根据一些简单的规则随时间逐步变化。有许多NKS系统并不是基于元胞自动机，但这种计算能很好地说明这个原理。元胞自动机是元胞（不是生物学意义的细胞）组成的1维、2维或3维阵列，其状态定期变化。在图2.3中，规则集由左边图示的8条规则组成。每条规则由1个大格子中的4个小格子描述。左边显示的规则相对右边的计算区域旋转了90度。第1条规则的意思是，如果某一步相邻的3个元胞都是白的，则中间元胞下一步是白的。第2条规则的意思是，如果3个相邻元胞最右边的是黑的，则中间元胞下一步会变成黑的，以此类推。根据这8条规则，显然只要3个元胞有1个是黑的，中间元胞下一步就是黑的，只有3个元胞都是白的，下一步的中间元胞才是白的。

从第1行元胞开始用规则集执行计算。你可以从任意的黑白图样开始。图2.3右边的初始行只有1个黑元胞，其余都是白的（第1步）。然后应用规则集254。产生的行有3个黑元胞，其余都是白的（第2步）。

继续执行，会基于第2行产生出第3行元胞图样（第3步）。这一行有5个黑元胞。计算可以一直继续下去。可以看出，从这个简单的输入数据开始（第一行），应用这个简单的规则，结果很简单，就是一个生长的黑三角形。规则集254无法产生出比输入行明显更复杂的图样。图2.4展示了用不同规则集实现的一个更有趣的元胞自动机。这个例子也是从只有一个黑元胞，其余全白的初始行开始。产生的图样被称为塞平斯基填充，这是数学中一个经典的分形图形。继续更新，会产生越来越大的三角形以及各种大小的小三角形。

如果元胞限于2种颜色（黑和白），并且每个元胞的颜色由上面的3个相邻元胞的颜色决定（如图2.3和2.4中的例子），则覆盖所有可能需要8条规则，因此总共有28=256种规则集。这些规则集大部分都只能产生简单图样，或是在第1行之后根本没有图样。少部分会产生更复杂的图样。

图2.5展示了规则110作用于只有单个黑元胞的输入行的结果，产生的图样规则与不规则并存。令人吃惊的是，规则110是通用性的。意思是说通过让规则110一遍又一遍作用于适当的输入行可以构造一台通用计算机。这个理论结果证明了通用计算逻辑上可以很简单，简单规则也能产生大的复杂性。

如果将元胞的颜色增加到3种（白、黑和灰），全部规则的数量从8条增加到27条，规则集的数量则增加到700多万种；但是同样，只有小部分规则会产生复杂的图样，大部分还是只能产生简单输出。

稍微改动一下方案，让元胞的颜色由上面3个相邻元胞的灰度均值决定。3个元胞的颜色均值有7级灰度，因此需要7条规则组成规则集：白（3白）、浅白灰（2白+灰）、白灰（白+2灰或2白+黑）、灰（3灰或白+灰+黑）、黑灰（2灰+黑或白+2黑）、深黑灰（灰+2黑）和黑（3黑）。这样总共有37=2187种规则集。同样，使用这种规则集的元胞机大部分都只能产生简单输出，但少数会产生相当有创意的图样。图2.6展示了规则集1635作用于只有一个黑元胞，其余全白的初始行产生的图样。

这4个简单的元胞机例子体现了简单规则反复作用于极为简单输入（这里是只有1个黑元胞，其余全白）会发生什么事情。显然对这一节标题中提出的问题的答案是，一些简单规则作用于简单输入能产生显著的输出复杂性。计算机学家设计了各种系统来测试将简单规则作用于简单输入，结论都是简单规则和输入的结合能产生显著的复杂性，但并不普遍，即便是在那些能产生复杂性的系统中，大部分规则集都只能产生简单结果。

图2.6说明了我们讨论过的几个信息度量并不符合我们日常的复杂性观念。所有人都会同意图中的图样很复杂。图2.6靠近底部的一行元胞似乎编码了很多信息，因为很复杂很长。但我们知道它的算法和香农信息度量很低，因为产生它的规则集和输入数据（1个黑元胞）很简单。因此，我们讨论过的这些信息度量并不是人类观察者所认识的复杂性的可靠指标。

NKS系统的行为通常用计算机进行探索，但我们看到的这4个例子也可以通过在桌上排列黑白灰卡片完成。后面我们会看到在试管中也有类似行为的系统。可以将其视为是通过自组装名为分子砖的小单元执行计算。这种计算的输出是物理结构。