复杂表现=计算能力？

     观察表明，生命游戏和110号基本规则都能从简单的初始位形演化出十分复杂的模式。两种元胞自动机都被证明能够进行通用计算，不严格地说：可以将任何一个计算机程序“编码”在初始位形中，自动机就会在一定时间后输出原程序的运行结果（当然还需要适当的解码）。例如，原则上我们可以用它们来运行任何你喜欢的电脑游戏，只要给予适当的接口。

      Wolfram等人认为，这种强大的计算能力解释了它们的复杂表现，反之亦然，具有类似表现的系统都有通用计算的潜质。他们进一步提出：既然这些通用计算的系统都是相互等价的，宇宙中所有的复杂现象都可以视作起源于110号基本规则这样简单的模型，从而达到一种特殊的大统一关系。

    这种等价关系显然是经验猜测，但将其当做定论认真对待的研究者大有人在。例如，混沌边缘的概念即来自于计算机科学家Langton对元胞自动机的研究，后者的结论是只有参数λ在某个临界点附近的元胞自动机才能进行通用计算。作者用刻意强调这种特性类似统计物理中的相变和临界现象，来试图泛化这一结论。

    可是其实原论文根本就没有作出通用计算的证明，只是证明它们的长期统计特征表现得“像”110号基本规则，也即是不能被归为简单的周期型或无明显规律的随机型而已。但这种程度的相似不足以将对110号规则图灵完备性的证明迁移到它们身上。或许由于Wolfram人为地将类似规则全归为相对重要的一类（即所谓Class 4），误导读者以为这类规则都共享着其中一员——即110号规则的特征。但自此，临界现象和计算能力间就被“复杂表现”给连上了稳固的纽带。

   要严格讨论计算能力的问题，首先要分析通用计算是不是复杂系统独有的显著特征。答案是否定的。

  即使是寻常的硬球撞击都和生命游戏或110号基本规则一样能进行通用计算，因为只凭弹性碰撞已经足以构造Toffoli逻辑门了，而这种门能组成的线路是图灵完备的。

  这点的推论之一是很多格点气体模型也可以进行通用计算（C.Moore, 1995），既然格点气体被认为是成功刻画了现实流体的特征（除了个别不现实的对称性缺失），Moore其实证明了：哪怕是生活中无处不在的气流都有生命游戏的计算潜力，后者根本不稀有，也不能作为系统复杂程度的说明。

   类似地，二维以上的伊辛模型也已被证明具备通用计算的能力，可这并不表明伊辛模型所能涵盖的大量体系都有110号基本规则的有趣特征，现实中也没有人随手拿起一块磁铁加热到居里点附近就当CPU用的。

    究其根本，乃是因为虽然我们证明了使体系做出有用计算的初始位形存在，但这类位形在自然环境下出现的概率可能是极低的，属于极端特征，所以从体系的典型表现中看不出来。因此，单独把通用计算这个特征拿出来，是没用的，这个体系或许会把大部分时间都花在平庸无奇的表现上。

    110号基本规则曾被嘲讽为“从未产生过像真实蚯蚓般复杂的现象”，但批评者的理由却是计算只在人工系统中存在，与自然界的复杂现象无关，这就比Wolfram错得更加离谱了。真实的原因是110号规则中这些现象是极度罕见的，以致于我们至今为止都没发现实现它的位形。但就自然界中计算无处不在这件事，Wolfram并没有说错。只不过他没有说：正因为这种无处不在，所以相关现象间可以完全不相似，即使从统计角度看也是如此。

    要说明一个自然体系能进行“计算”，需要至少两个条件：

（1）计算是高效的。如果运行一个程序需要设置的体系基本单元（粒子/元胞）数目十分巨大，那么对应该程序的初始位形随机出现的几率就很低。从而只有透过外界的精密操作才能让系统计算该程序。

（2）计算是可逆的。根据Landauer原理，计算非一一的逻辑映射的系统必须是耗散的，于是持续的不可逆计算都需要相适配的外在驱动机制（我的电脑需要以适当的设备供电才能工作），因此通常只能人工实现。

   110号基本规则和生命游戏虽然图灵完备，但它们不是可逆的。

    反过来，能产生复杂表现的体系也不一定能做通用计算，这点即使是限制在元胞自动机内部也是成立的。

   不过，如果一个元胞自动机规则表现复杂，那么严格证明它不能做通用计算会比较困难。

   虽然如此，判断逻辑映射是否一一却相对容易。而证明计算的低效则可以通过高效仿真这种自动机来实现。例如，如果自动机在t步内的行为总可以被运行时间log t的程序完全预测，则该自动机就不可能做高效的通用计算，否则预测它的程序就可以在对数时间内做到这些事，但对数时间不可能实现线性时间的所有任务。

  总之，自然系统的计算能力和复杂表现分开来看都是很有价值的课题，但两者间的联系就未必如此了。