为什么需要长程序？

我们大部分人在思考计算时，不会想到自组装砖块或NKS系统，甚至不会想到任何基于简单规则的物理系统；相反，我们想到的是需要长程序的应用，例如字处理软件和电子表格。根据我们的经验，大部分有用的计算机应用都需要长程序。通过研究一切可构想计算的所有可能的输出，数学家证明了大多数都需要长输入才能产生。考虑到计算和物理组装的密切关联，有理由认为我们想得到的许多事物也会需要长程序。对于NKS和拼砌系统，由于规则和砖块类型有限，这意味着大多数可能的行（输出）如果没有复杂的种子行就无法实现。因此虽然元胞机规则集90、110和1635产生的行很复杂（图2.4、图2.5和图2.6），如果种子行简单，大多数可构想的行永远也无法通过这些计算产生。大部分时候，要得到一个特定的行，你需要从一个仔细设计并且已经很复杂的种子行开始。种子行的细节决定了任何给定规则集的产出。再次强调前面说过的，计算机理论告诉我们，如果输入（规则和种子）简单，大多数可构想的结果都无法通过确定性过程产生。

好的一面是，在符号语言的领域内只要有合适的长程序似乎就能生成一切。经常使用电脑的人对此有经验。长程序能产生令人炫目的输出，字处理、电子表格、网页编辑和计算机游戏只是一小部分例子。大多数日常计算机应用就是无法用短程序实现，再巧妙的设计也不行。

这个简单的原理几乎肯定对物理世界有效。想一想生命和许多人类技术产品的形成。生物和汽车的产生都需要长而且复杂的指令。根据计算机科学的原理，我们可以想见，如果只依靠化学和物理定律，没有附加的信息，这类事物是根本不可能出现的。这就是指令的作用。

总结一下这一章给出的许多概念，计算可以被认为是逻辑规则作用于已存在的状态产生新状态的过程。至于状态是发生在计算机电路里，还是含有分子砖的试管里，或是活细胞里，抑或是自组装的拼图，并不重要。

系统的状态之间如果可以相互区分，系统就能携带信息。系统状态可以表示其他系统的状态，这一点很重要。这样意义就能从一个系统传递到另一个系统。信息和意义的概念与日常用法纠缠不清。在第1和第2章我们遇到了定义和度量信息的3种方法。用长度度量很简单，但无法体现全部；香农信息是基于状态的概率；算法信息则是基于过程（产生对象的计算）。在确定性计算中长度可以增长，但算法信息和香农信息不会。所有这3种都可以归结为计算的结果。还没有人提出过意义的量化度量。

计算的一个重要原理是显著的复杂性可以通过简单规则反复作用于简单初始条件产生。NKS和DNA拼砌系统提供了实在的例子，化学和物理定律反复作用于物质简单的初始状态形成的物理结构也说明了这一点。下一章我们会看到这种结构的一些例子。

计算机科学的另一个重要原理是一些复杂事物无法通过简单输入和简单规则的计算产生。生命以及许多生命的产物，包括人类社会和技术，似乎都需要长程序。长指令在物理世界扮演的角色就好像长程序在计算世界扮演的角色。没有它们，一些复杂的对象和行为就不可能产生。第4章我们会看到一些这样的例子。