第七章柏拉图主义 (2-2)

虽然图灵引入了带有Oracle的图灵机来处理更高复杂度层次上的计算，但那显然已经脱离现实世界能够实现的范畴了（尚未发现有哪个物理过程能记录完整的无穷集合）。递归论学到了这部分，我竟然产生了和学集合论时类似的挫败感，追求更大的基数和追求更高的跃迁层次又有什么区别呢？

算法随机性是递归论得到极大应用的一个方向之一，他试图回答什么是直观意义上的“随机实数”。对逻辑学家来说，实数通常指无穷0-1序列或者无穷的自然数序列。所以回答什么样的实数是“随机的”，只要回答什么样的0-1序列是随机的即可。类似于“可计算”的概念，关于随机性这个概念也出现了很多种诠释。

柯尔莫哥洛夫试图用信息的可压缩性描述随机性，如果一个有穷的0-1序列能够被图灵机压缩为一个很短的序列，那可以认为它不怎么具有随机性。后来又出现了马丁洛夫随机性的刻画，他们认为如果一个无穷0-1序列能够通过一系列的能行的测试，那么它应该被认为是具有随机性的（比如0和1出现的概率应该一半一半，或者满足大数定律等等）。

还有一种对随机性的刻画是基于一种对赌策略的，鞅是一种关于赌局的策略，赌局的规则是猜硬币，正面为0，反面为1，双发押上上一局的所有筹码，猜对了会获得筹码的两倍报酬。对每一局，鞅会给出一个策略押0还是1，如果赌局一直下去，我方的筹码越来越多，那么我就赢了。可以想象，如果每局掷出0或者1得到的序列真的是随机的，那么不论我用什么策略，都不可能赢。

这几个刻画都不可避免地用到递归论的能行可计算的概念。而且能够证明三种对随机性的刻画是等价的，由它们得到同一个0-1序列集类。但这个集类并不复杂，仅仅只是Σ⁰₂ 的，而且由它们定义的一个典型的随机数：蔡廷常数 Ω ，虽然具有足够强的随机性，但却是可以从小到大能行地逼近的。综合这些原因，对随机性的刻画似乎总是得不到普遍的认可。

究其原因，我认为，如果把实数（或者自然数的幂集、无穷0-1序列等）看成是广袤无际的海洋。那么递归论（可计算性理论）就是浅海柔软的海床，那里有我们能触及到的奇珍，蜿蜒曲折的珊瑚和形态各异的物种争奇斗艳，那里是明亮且平坦的。但在海床的尽头，是深不见底的深海，是充满未知和危险的裂隙，阳光无能为力地消失在看不到尽头的蓝色之中。我们也许意识到了深海是具有层次结构的，那里应该是“随机性”的栖息地，但用浅海的藻泥描述的随机归根结底也不可能探入到更深的层次。如果来自深海里的信息选择不向我们展示自身，那看起来我们对它们的了解无非也就只能停留在如此浅显的层次。

数学联邦政治世界观提示您：看后求收藏（同人小说网http://tongren.me），接着再看更方便。