算法与概率的联姻
要研究由精确无误的计算规则产生的数列,所罗门诺夫复杂度的确是个美妙的概念。然而,一旦我们转向经验科学,模糊性和误差的入侵就无法避免。如果数列对应的是物理量的测量或者社会科学中的数据,我们就应该预料到数列的这些项不会与 2 的次方精确吻合。假设我们得到的数列实际上是 0.9, 2, 4.1, 7.9, 15.8,我们现在希望在测量误差为 0.2 左右的情况下预测出一个接近 31 或者 32 的值。
这时就必须用到概率的语言了。尤其是在预测时,与其进行确定性的预测,比如预测数列的下一项恰好是 32,我们更希望做出概率性的预测。通常来说,我们认为 32 是非常可能的,但 31.9 或 32.2 等数字也很有可能。因此,一个定义良好的概率性预测应能计算数列中下一项的所有候选数值的正确的出现概率。
将哥德尔、丘奇和图灵的可计算性理论与贝叶斯、普赖斯和拉普拉斯的概率理论结合起来,我们就得到了关于“一个理论是什么”的全新定义。这个定义正是所罗门诺夫智慧的结晶。对于所罗门诺夫来说,理论就是图灵机上的一段源代码,给定某个数列,它就会计算这个数列出现的概率。
此前为使叙述简单易懂,我只谈到了数列。然而,根据我们之后会谈到的香农的研究工作,所有数据序列都可以翻译成 0 和 1 组成的数列。这些数列又叫作 0 - 1 序列。因此,计算机科学家认为,一般而言,感官接收的所有数据,无论是眼睛看到的图像、耳朵听到的声音、鼻子闻到的气味,还是中耳测定的平衡感,都可以用一个(非常长的)由 0 和 1 组成的数列 6 描述 [7]。对于所罗门诺夫来说,一个理论就是一个算法,给定某个有限 0 - 1 序列,就能计算出它的概率。
6感官接收的信息量估计大概在每秒 和 比特之间,虽然这些信息很快就被大大压缩了。
这种关于理论的定义可能看起来太狭隘。许多公认的科学理论,比如演化理论和牛顿运动定律,看起来都不是能计算 0-1 序列概率的算法。的确如此。从某种意义上来说,我们可以认为这些理论按照所罗门诺夫的标准是过于含混、模糊或者不完整的。
然而,有一个更有趣的观点:现在真正进行概率计算的,正是依据这些理论思考的大脑。我们可以对这些大脑讲述一段演化的历史,然后它就会回答这段历史可信度的估计值。然而,如果我们相信丘奇–图灵论题的话,这些大脑进行的不过是一台拥有适当源代码的图灵机也可以做到的计算。因为我们讲述的演化史可以编码为一串 0 和 1 的数列,所以,一般来说科研工作者(在这个例子中是演化学家)说到底离所罗门诺夫的体系也没有太遥远。
可以说,演化理论和牛顿运动定律都对应着一组子程序,进行预测的算法可以调用这些子程序。实际上,科学中的理论常常就是一组方程,计算机科学家能够利用算法结构为它们建模,然后将这些结构与解方程的算法结合起来,这些算法我们在学校里都学过。这样一来,我们就得到了不同的代码库,对于能进行可信预测的算法来说当然非常有用。
所以我们可以认为,这些至关重要的代码库对应着某种基本法则。科研工作者的日常用语经常将不随时间变化的理论与用于预测的额外数据分开。比如说,物理学家会区分物理定律和宇宙的物理状态,计算机科学家也经常将算法的指令与运行算法时所用的数据区分开来。我们也倾向于认为物理定律拥有一种独立于任何物理状态的真理性(或者有效性)。
然而,图灵证明的正是定律和状态在本质上没有区别。毕竟所有指令序列(或物理定律)都可以编码成用于通用图灵机的数据。跟数据一样,任何指令序列(或物理定律)也只是一段信息。约翰·冯·诺伊曼赖以构建现代计算机体系结构的基本原则也正是这一点,它保证了得到的结果是如假包换的通用图灵机。在这一体系结构中,指令和数据都是计算机储存中的信息,而它们之间没有本质上的区别 [8]。
至此,所罗门诺夫认为,唯一值得关注的信息就是拥有预测能力的算法的描述。要求算法具有预测能力,是为了明确指出对于奥卡姆剃刀的应用至关重要的“理论的复杂度”概念。这是因为,物理定律本身可能看起来很简单: 这个公式只需要寥寥几个符号,“都是因为外星人”这句话也不长。但这是因为这些法则本身并不具有预测能力。要拥有预测能力,它们就必须与详细程度不等的宇宙物理状态描述结合起来。
正是这一点让我们可以区分不同定律的复杂度。有些定律需要对宇宙状态极为详细的描述才能输出预测,最终就构成了所罗门诺夫复杂度极高的复杂结构。用算法的术语来说,这种定律与对物理状态的描述组合成一段极长的源代码。反之,那些通过对宇宙物理状态的非常简略的描述就可以做出预测的理论远远简单得多,因而在先验上也更可信。
总而言之,所罗门诺夫认为,值得考虑的理论应该包含对宇宙物理状态的(部分)描述,因为它首先必须具有预测能力。在理想情况下,这种理论也应该考虑到给定宇宙物理状态的不确定性,但最重要的是,最终它必须做出(概率性的)预测。毕竟一个理论应该只有给出可计算的预测才值得考虑。这是因为,如果我们相信丘奇–图灵论题的话,只有这样的预测才能在这个宇宙之中实现。
我们如果跟随所罗门诺夫的脚步,那就也要相信所有值得考虑的理论组成的集合恰好是所有计算 0-1 序列概率的算法组成的集合。正如阿伦森认为“你如果花足够长的时间来思考,最终就会得出结论:所有计算都可以通过图灵机完成”。我现在也这样说,你如果花足够长的时间来思考,最终就会得出结论:任何具有预测能力的理论都是所罗门诺夫意义上的理论。