元数学：复杂度、随机性与不完备（一） (12-4)

他给了我一些他的论文。其中一篇是关于计算的，是关于 Π 和 e 的十进制展开式中不同数位的分布，它们似乎是正规的......另一篇论文是理论性的，是关于有理数中的数位，周期性的十进制展开式。斯通汉姆能够证明，对于某些有理数 m/n 来说，数位是等分布的，但要符合 m 和 n 的条件，我已经记不清了。

就这样，那是我们唯一一次见面。

几年过去了，我想出了停止概率（halting probability）Ω。我再也没听说过斯通哈姆，直到我从博尔文和贝利在《实验数学》中关于正规数的章节中得知，斯通哈姆真的做到了！令人惊奇的是，我们都实现了自己的目标！

贝利和克兰德尔在 2003 年自己的研究过程中发现，30 年前，现已去世的斯通哈姆（这是沃尔夫拉姆书中的信息）成功地找到了正规数的第一个 "自然"例，据我所知，这是正规数的第一个 "自然"例子。

斯通哈姆看起来像是刘维尔(Liouville)的翻版，他没能证明Π 或 e 是正规的。但他证明了一个自然无穷级数的和是2 正规(2-normal)的，也就是说，对于基 2 (base-2)中每种可能大小的比特块而言都是正规的！

我和他都找到了我们要找的东西！真让人高兴！

本章我将告诉你我们是如何做到的。但首先，作为热身练习，为了让大家进入状态，我想证明图灵的停止问题是无解的。在研究我的停止概率Ω之前，我们应该先证明这一点。

为此，我想证明，除了有限次(finitely often)，你无法证明一个程序是优美的。信不信由你，这个证明的想法其实来自埃米尔-波莱尔（Émile Borel），也就是之前那个波莱尔。虽然我最初自己找到这个证明时并没有意识到这一点......

所以，让我先告诉你波莱尔的美丽想法。

波莱尔的随机性不确定悖论

我非常清晰地记得，我是在波莱尔一本关于概率论基本思想的书的英译本中读到我将要向你们解释的这个思想的。不幸的是，我再也找不到那本书了，也找不到波莱尔下面的论述，即关于任何对一个随机性确定概念（a definitive notion of randomness）之给出的尝试的悖论。

因此，这有可能是一段虚假的记忆，也许是我曾经做过的一个梦，有时对我来说似乎是真实的，或者是我多年来以某种方式编造的一段 "再加工"记忆。

不过，波莱尔著作颇丰，而且对这些问题非常感兴趣，所以这可能就在他的作品中！如果您找到了，请告诉我！

撇开这一点不谈，让我和大家分享一下我对波莱尔讨论的一个问题的回忆，这个问题是任何试图定义随机性概念的尝试都不可避免地会出现的。

假设你能以某种方式区分其小数点后数字组成随机序列的整数 同 其小数点后数字无法做到的整数。

现在想想第一个符合你的随机性定义的 N 位数。但这个特定的数字相当不典型，因为它恰好是第一个具有特定性质的 N 位数！

问题在于，随机（random）的意思是 "典型、不突出、没有显著特征"。但是，如果你能定义随机性，那么为随机（being random）之属性就变成了你可以用以证明某些数字是非典型的、从"人群"中脱颖而出的又一个特征！

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