元数学：复杂度、随机性与不完备（一）

目录

不可还原的真理与希腊的理性理想 ▹

掷硬币、随机性VS原因、无理真、不相关的事实 ▹

纽约市立大学随机性对话，1965年 ▹

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

为什么不能证明程序“优美”？ ▹

回到图灵停机问题 ▹

Ω作为停止问题之预言 ▹

再谈波莱尔正规数 ▹

用二元方程求Ω的比特 ▹

为什么对随机实数Ω 如此感兴趣？ ▹

故事的寓意是什么？ ▹

反对利己主义 ▹

原文选自 META MATH！The Quest For Omega 第6章COMPLEXITY, RANDOMNESS & INCOMPLETENESS

作者：GREGORY CHAITIN（2006）

在第二章中，我向你展示了图灵的不完备性方法。现在，让我向你们展示我是如何做到这一点的......

我对本章的两个不完备性结果感到非常自豪！它们是AIT(算法信息论）皇冠上的明珠，是最好（或最差）的不完备性结果，是最令人震惊的结果，是最具破坏性的结果，是最具启发性的结果！此外，它们还是数字哲学观点的结果，这种观点可以追溯到莱布尼茨，我在第三章中也有描述。这就是为什么这些结果与哥德尔（1931）和图灵（1936）的经典不完备性结果如此惊人地不同。

不可还原的真理与希腊的理性理想

首先，我想向大家介绍一下 "逻辑不可还原性 （logical irreducibility）"这一非常危险的观点...

Mathematics：axioms → Computer → theorems

我们将在本章中看到，传统的数学概念是完全错误的：将事物简化为公理，压缩（compression）。不，有时这根本行不通。本章展示的不可还原的数学事实——Ω的比特/位数（the bits ofΩ）——无法从任何比它们本身更简单的原理中推导出来。

因此，关于证明之效用的普通概念于其而言乃失效的——证明，在这些情况下根本无济于事。简单的公理与复杂的结果才是证明的用武之地。但在这里，公理必须同结果一样复杂。那么，使用推理（reasoning）还有什么意义呢？

换一种说法： 数学的普通概念是在数学世界中寻找结构和规律，寻找理论。但理论意味着压缩，而这里不可能有压缩——在数学世界的这个特殊角落里，根本没有结构或规律。

既然没有压缩，就不可能理解这些数学事实！

总之...

When Is Reasoning Useful?

“Axioms=Theorems”implies reasoning is useless!

“Axioms ≪ Theorems”implies compression & comprehension!

如果公理的大小（size）同有趣定理（interesting theorems）的大小完全相等，那么推理是绝对无用的。但如果公理远小于有趣定理，那么我们就有了大量的压缩，因此也就有了大量的理解！

希尔伯特将这一传统发挥到了极致，他认为有限复杂度的一个单个 FAS（形式公理系统），即有限比特的信息（a single FAS of finite complexity, a finite number of bits of information），必须足以产生所有的数学真理。他相信万物的终极理论，至少对于纯数学世界是如此。丰富、无限、充满想象力、开放式的数学世界，全部压缩成有限的比特数！这将是多么壮观的压缩啊！人类理性力量的丰碑！

掷硬币、随机性VS原因、无理真、不相关的事实

现在，与希腊的纯粹理性理想截然相反的是：独立抛掷一枚公平的硬币，这是物理学中的一个概念！

一枚 "公平"的硬币意味着正面和反面的可能性一样大。"独立"是指一次抛硬币的结果不会影响下一次的结果。

因此，抛硬币的每一个结果都是独一无二的原子事实，与其他任何事实都没有联系：与之前的任何结果都没有联系，与未来的任何结果也没有联系。

如果我们面对的是一枚公平硬币的独立抛掷，那么知道前一百万次抛掷硬币的结果，对我们预测下一次结果毫无帮助。同样，如果我们能知道所有偶数结果（第 2 次掷硬币、第 4 次掷硬币、第 6 次掷硬币），也无助于预测任何奇数结果（第 1 次掷硬币、第 3 次掷硬币、第 5 次掷硬币）。

这种无限次独立掷出一枚公平硬币的想法听起来似乎很简单，就像一个玩具物理模型，但对于任何试图建立理性世界观的人来说，这都是一个严峻的挑战，甚至是一场可怕的噩梦！因为每一个结果都是一个无理真（true for no reason），其只能通过意外而为真（true only by accident）！

Rationalist Worldview

In the physical world，everything happens for a reason. In the world of math，everything is true for a reason.

The universe is comprehensible，logical!

Kurt Gödel subscribed to this philosophical position.

因此，像莱布尼茨和沃尔夫拉姆这样的理性主义者一直反对物理随机性，或莱布尼茨所说的 "偶然事件"，因为它们无法用理性加以理解，它们完全驳斥了理性的力量。莱布尼茨解决问题的办法是宣称，偶然事件之所以为真也是有理由的，但在这种情况下，实际上存在着一系列无限的原因，一个无限的因果链条，虽然完全超出了人类的理解力，但却完全没有超出神性思维之理解力。沃尔夫拉姆解决这个问题的办法是，我们在世界上看到的所有表面上的随机性，实际上只是伪随机性。它看似随机，但实际上是简单规律的结果，就像Π=3.1415926 .....的数字看似随机一样。

尽管如此，目前量子力学要求物理世界具有真正的内在随机性、真正的不可预测性，混沌理论甚至表明，如果你相信无限精确的实数，相信对初始条件的高度敏感性能够将初始条件中的随机比特迅速扩大到宏观领域，那么在经典的确定性物理学中实际上存在着一种略微温和的随机性......

物理学家卡尔-斯沃齐尔（Karl Svozil）对这些问题持以下有趣的立场。斯沃齐尔倾向于经典的决定论，并对爱因斯坦的 "上帝不掷骰子"断言表示同情。斯沃齐尔承认，在目前的状态下，量子理论包含随机性。但他认为这只是暂时的，一些新的、更深层次的隐变量(hidden-variable)理论最终会恢复物理学的确定性与规律性。另一方面，斯沃齐尔认为，正如他所说的那样，Ω表明在纯数学的（不真实的）心理思维幻境中存在着真正的随机性！

纽约市立大学随机性对话，1965 年

作为这个故事的背景资料，我首先要告诉大家，一个世纪前，波莱尔（Borel）提出了随机实数的数学定义，事实上，有无限多的变体定义。他把这种实数称为 "正规（normal）"数。就是这个波莱尔，在 1927 年发明了我们在第五章讨论过的 "全知实数"（know-it-all-real）。1909 年，他证明了大多数实数必须满足他对正规性的所有变式定义。不满足其中任何一个定义的概率为零。

波莱尔对正规实数的定义是什么？嗯，它是一个实数，具有每一个可能的数字都以相同的极限频率出现的特性：从长远来看，正好是 10%。这就是所谓的 "简单"10-normal。而 10-normal tout court 的意思是，对于每个 k，实数的基十展开(base-ten expansion)都有 10k 个可能的 k 个连续数字块（the 10k possible blocks of k successive digits），每个数字块的极限相对频率都是完全相同的 1/10k。所有可能的 k 个连续数字块在长期出现的可能性完全相同，对于 k =1、2、3......，每 k 都是这种情况。最后，还有一种纯粹的 "正规"，即用任何基数（而不仅仅是基十数）书写的实数都具有这种性质。换句话说，"正规"意味着它是 2-normal, 3-normal, 4-normal，以此类推。

因此，大多数实数都是正整数，概率为 1（Borel，1909 年）。但如果我们想展示一个特定的正整数呢？似乎没有理由怀疑 Π 和 e 是正整数，但至今没有人知道如何证明这一点。

好了，以上就是有关波莱尔正规性的背景信息。现在让我们把时间快进到 1965 年。

我是城市学院的一名本科生，刚上大二。我正在撰写和修改我第一篇关于随机性的论文。我对随机性的定义与波莱尔的完全不同。它是我在本书中讨论过的要求更高的定义，基于算法不可压缩性的理念，基于研究计算机程序大小的理念。事实上，它是基于莱布尼茨在 1686 年的一句话，虽然我当时并不知道。这是我在 1966 年和 1969 年发表在 ACM 期刊上的论文。

为了让我把这些东西准备出版，院长让我不用去上课，城市学院很快就传开了，说我正在研究随机性的新定义。原来，城市学院有一位教授理查德-斯通汉姆（Richard Stoneham），我从来没有上过他的课，他对正规数非常感兴趣。

我们在他的办公室见了面，他的办公室位于奇妙的旧石伪哥特式的谢帕德大厅，我向他解释说，我正在研究随机性的定义，这个定义意味着波莱尔正规性，而且大多数实数都能满足这个定义，概率为 1。

他解释说，他有兴趣证明像 Π 或 e 这样的特定数字是正规的。他想证明某些著名的数学对象已经包含随机性，即波莱尔正规性，而不是某种新的随机性。我反驳说，像 Π 或 e 这样的数无法满足我对随机性的更苛刻的定义，因为它们是可计算的实数，因此是可压缩的。

他给了我一些他的论文。其中一篇是关于计算的，是关于 Π 和 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）之属性就变成了你可以用以证明某些数字是非典型的、从"人群"中脱颖而出的又一个特征！

这样，你就得到了一个随机性之概念的层次结构：你开始使用的那个概念，然后是下一个概念，然后是由此派生出来的一个概念，以此类推......而其中的每一个概念都是根据前面的随机性定义派生出来的，就像其他可以用来对数字进行分类的特征一样！

波莱尔的结论是，随机性不可能有一个确定的定义。你无法定义一个包罗万象的随机性概念。随机性是一个模糊的概念，它有一些自相矛盾之处，很难把握。这就需要决定我们的要求有多高。你必须决定一个分界线，你必须说 "够了"，让我们把它看作是随机的。

让我尝试用一些图像来解释这一点，这些图像绝对不是出现在我那也许颇为错误的波莱尔忆述中。

当你将随机性的概念固定在脑海中的那一刻，这个心理行为就会使这个概念失效，并创造出一个新的要求更高的随机性概念......所以，把随机性固定在脑海中，就好比你不眨眼、不动眼地盯着某个东西看。如果你这样做了，场景就会开始从你的视野中成片消失。要想看到某样东西，你就必须不断移动你的眼睛，改变你的注意力焦点......

你越努力盯着随机事物，看到的就越少！这就有点像在晚上用望远镜看微弱的物体，你不能直接盯着它们看，而是要把视线移到一旁，这样视网膜的分辨率会更低，对颜色的敏感度也会更低，但你能看到更微弱的物体......

我将归功于波莱尔的这一讨论，实际上包含了我现在要给出的证明的思想萌芽，即你无法证明一个计算机程序是 "优美的"，也就是说，它是具备产生如此输出结果的能力的程序中，最小的一个。更准确地说，如果没有比它更小的程序能产生相同的输出，那么这个程序就是优美的。你看，可能会出现平局，可能会有几个不同的程序具有完全相同的最小可能大小，并产生相同的输出结果。

从理论的角度来看，正如第三章所讨论的那样，一个优美的程序是对其输出的最佳压缩，它是——被视为实验数据的——输出之最简单科学理论。

因此，如果这个计算机程序的输出是整个宇宙，那么它的优美程序就是最优的TOE，最优的万物理论，没有冗余元素的TOE，最好的TOE，莱布尼茨会说，完美的上帝会用它来创造那个特定的宇宙。

为什么不能证明程序 "优美"？

因此，让我们考虑希尔伯特/图灵/后形式公理系统 FAS，它（如第二章所述）对我们来说只是一个生成所有定理的程序。我们假定，这个程序是生成那组特定定理的程序中，最小的一个。因此，这个程序的大小正是该理论之程序大小复杂度（the program-size complexity）。绝对没有冗余！

好了，这就是我们如何通过 FAS 所包含的比特信息的多少加以衡量其威力。正如你现在看到的，这真的很有效，它真的给了我们新的启示。

在上一节讨论的波莱尔悖论的基础上，考虑一下这个计算机程序...

Paradoxical Program P：

The output of P is the same as the output of

the first provably elegant program Q that you encounter (as you generate all the theorems of your chosen FAS) that is larger than P.

我们为什么要利用波莱尔悖论呢？因为我们的想法是，如果我们能证明一个程序是优美的，那么我们就能找到一个更小的程序，产生同样的输出，这是矛盾的！波莱尔悖论的意思是，如果我们能定义随机性，那么我们就能找出一个完全不是随机的随机数，这是矛盾的。因此，我认为这两个证明，即 波莱尔的非正式悖论和这个实际定理，或者更准确地说，元定理，是一脉相承的。

换句话说，P 会生成 FAS 的所有定理，直到它找到一个证明，证明某个程序 Q 是优美的，而且 Q 的大小必须大于 P 的大小。如果 P 能找到这样的 Q，那么它就运行 Q，并将 Q 的输出作为自己的输出。

自相矛盾。因为 P 太小，无法产生与 Q 相同的输出，因为 P 比 Q 小，而 Q 应该是优美的（假设 FAS 中证明的所有定理都是正确的，都是真的）！避免这一矛盾的唯一方法就是 P 永远找不到 Q，因为在这个 FAS 中，并没有一个比 P 大的程序 Q 是优美的（no program Q that's larger than P is ever shown to be elegant in this FAS）。

因此，使用这个 FAS，你无法证明如果程序 Q 比 P 大，它就是优美的。因此，在这个FAS中，你无法证明超出（more than）有限多个特定程序是优美的（所以停止问题是无解的，我们将在下一节看到）。

而 P 只是一个固定的比特数（a fixed number of bits），大于我们使用的 FAS。P 主要包含生成所有定理的指令，也就是可变部分，再加上一点固定部分，用于过滤定理并进行上述证明。

因此，基本原理是，如果一个程序的大小大于生成 FAS 中所有定理的程序的大小，那么你就无法证明它是优美的。换言之，如果程序大于你的 FAS 的程序大小复杂度，那么你就无法证明这个程序是优美的！不可能

你看，能够测量一个 FAS 的复杂度，能够测量它包含了多少位/比特的信息，是多么有用啊？

默许假设： 在本讨论中，我们假定 FAS 是合理的，也就是说，我们假定它所证明的所有定理都是真的。

注意： 我们还没有真正拥有完全的不可还原性，因为 "P 是优美的"、"Q 是优美的"、"R 是优美的 "这些不同的情况并不是相互独立的。事实上，你可以通过同一个N比特公理来确定所有小于N比特的优美程序，这个公理告诉你哪个小于N比特的程序停止时间最长。你知道如何做到这一点吗？

不过，在我们解决这个问题并用停止概率Ω的比特来实现完全不可还原性之前，让我们先暂停一下，推导出一个有用的推论。

回到图灵停机问题

这里有一个直接的结果，它是我们刚刚确定的事实的一个推论，即你不可能机械地找到超过有限的多个优美程序（ you can't mechanically find more than finitely many elegant programs）：

没有算法能解决停止问题，即决定给定程序是否停止。反证法证明：因为如果有这样一种算法，我们就能用它找到所有优美的程序。方法是依次检查每个程序，看它是否停止，然后运行那些停止的程序，看它们产生了什么，最后只保留你找到的第一个产生给定输出的程序。如果你按大小顺序查看所有程序，就能准确地找到所有优美的程序（并列除外，并列并不重要，我们可以忽略不计）。

事实上，我们刚刚已经证明，如果我们的停止问题算法，其大小是N比特，那么一定有一个程序是永远不会停止的，而且这个程序的大小最多只是比N比特大几个比特，但我们不能用我们的N比特停止问题算法加以决定这个程序永远不会停止。(我们假设停止问题算法宁愿永远不给出答案，也不愿给出错误答案。这种算法可以重新解释为 FAS）。

因此，我们刚刚证明了图灵著名的 1936 结果，与他最初证明的方式完全不同，我们使用的是程序大小、算法信息和软件复杂度的概念。在我找到的所有图灵结果的证明中，这个是我最喜欢的。

现在我必须坦白另一件事。我认为，在找到自己的证明之前，你无法真正理解一个数学结果。读别人的证明不如自己找证明。事实上，我认识的一位优秀数学家罗伯特-索洛维从不让我向他解释证明。他总是坚持只让我告诉他结果的陈述，然后他自己去思考！我对此印象深刻！

这是我能找到的对图灵结果的最直接、最直接、最基本的证明。我试图抓住问题的核心，去掉所有杂乱无章的东西，去掉所有妨碍理解的外围细节。

这也意味着，我们在第二章讨论希尔伯特第10个问题时缺失的部分现在已经补上了。

为什么停止问题很有趣？嗯，因为在第二章中，我们证明了如果停止问题无法解决，那么希尔伯特第 10 个问题也就无法解决，也就没有算法来决定二叉方程是否有解。事实上，图灵的停止问题与希尔伯特的第 10 个问题是等价的，从这个意义上说，任何一个问题的解都会自动地提供（provide）/担保（entail）另一个问题的解。

停止概率Ω和自限制程序

现在，我们将真正获得不可还原的数学事实，即 "无理由真（are true for no reason）"的数学事实，它在纯数学中尽可能地模拟了公平硬币的独立抛掷：这是停止概率Ω之基二扩展（base-two expansion）的比特！你无法证明一个程序是优美的，这个美丽而富有启发性的事实只是一个热身练习！

与其像图灵那样只看一个程序，问它是否停止，不如把所有可能的程序装进袋子里，摇一摇，闭上眼睛，挑出一个程序。我们随机选择的这个程序最终停止的概率是多少？让我们用一个介于 0 和 1 之间的无限精确二进制实数来表示这个概率。瞧！它的位数就是我们独立的数学事实。

The Halting Probability Ω

You run a program chosen by chance on a fixed computer. Each time the computer requests the next bit of the program. flip a coin to generate it，using independent tosses of a fair coin The computer must decide by itself when to stop reading the program. This forces the program to be self-delimiting

binary information.

You sum for each program that halts

the probability of getting precisely

that program by chance：

Ω＝∑ program p halts 2—(size in bits of p)

Each k-bit self-delimiting program p that halts

contributes 1/2ᵏ to the value of Ω.

自限制程序(The self-delimiting program)的限制性条款至关重要： 否则，停止概率必须针对每个特定大小的程序加以定义，而不能针对任意大小的所有程序来定义。

为了让 Ω 看起来更真实，我想指出，你可以从下往上计算它的极限：

Nth Approximation to Ω

Run each program up to N bits in size for N seconds.

Then each k-bit program you discover that halts contributes 1/2ᵏ to this approximate value for Ω.

These approximate values get bigger and bigger(slowly!) and they approach Ω more and more closely，from below.

lst approx. ≤ 2nd approx. ≤ 3rd approx.≤ ... ≤ Ω

我在《数学的极限（The Limits of Mathematics）》一书中用 LISP 编写了这一过程。使用我在书中介绍的特殊 LISP （同语系）语言，给出 Ω 作为 N 的函数的近似值的 LISP 函数大约有半页代码。

然而，这个过程收敛到 Ω 的速度非常非常慢。事实上，你永远无法知道你有多接近，因此这是一种相当弱的收敛。

通常情况下，要使一个实数的近似值有用，你必须知道它们与所近似的东西有多接近，你必须知道所谓的 "收敛率"，或者有所谓的 "可计算的收敛调节器"。但在这里，我们没有这些，只有一个有理数序列，它非常缓慢地越来越接近Ω，但我们却无法精确地知道，在这个无休止的计算中，我们在某一点上离Ω有多近。

尽管如此，这些近似值还是非常有用的： 在下一节中，我们将利用它们来证明 Ω 是一个算法上 "随机 "或 "不可还原"的实数。在本章稍后部分，我们将用它们来构造 Ω 位的二阶方程。

Ω作为停止问题之预言

为什么Ω的比特是不可还原的数学事实？这是因为我们可以利用Ω的前N比特(the first N bits)来解决所有——大小不超过N比特的——程序的停止问题。这就是 N 比特的信息，而 Ω 的前 N 比特因此是这些信息的非冗余再现。

How much information is there in the first N bits of Ω?

Given the first N bits of Ω. get better and better approximations for Ω as indicated in the previous section，until the first N bits of the approximate value are correct.

At that point you’ve seen every program up to N bits long

that ever halts. Output something not included in any of the output produced by all these programs that halt. It cannot have been produced using any program having less than or equal to N bits.

Therefore the first N bits of Ω cannot be produced with any program having substantially less than N bits，and Ω satisfies the definition of a “random” or“irreducible” real number given in Chapter Five：

H(the first N bits of ‘’)＞N – c

我在《数学的极限》一书中用 LISP 写了这个过程。如果给定任何计算 Ω 的前 N 比特的程序，就能产生复杂度大于 N 比特的 LISP 函数，使用我在该书中介绍的特殊 LISP 语言，大约只需一页代码。对于所有 N，H（Ω 的前 N 位）都大于 N -c。因此，Ω 的前 N 位的程序大小复杂度永远不会低于 N。

既然我们知道 Ω 是一个算法上 "随机"或 "不可还原"的实数，那么第五章中给出的，关于 FAS 只能确定这样一个数的有限位/比特的论证就立即适用于 Ω。其基本思想是，如果 Ω 的 K 比特可以被 "压缩"到一个远远小于 K 位的 FAS 中，那么 Ω 就不是真正的不可还原。事实上，利用第五章的论证，我们可以准确地说出给定的 FAS 可以确定 Ω 的多少比特。下面是最终结果

A FAS can only determine

as many bits of Ω as its complexity

As we showed in Chapter Five，there is (another)constant c such that a formal axiomatic system FAS with program-size complexity H(FAS) can never determine more than H(FAS)＋c bits of the value for Ω.

These are theorems of the form“The 39th bit of Ω is 0” or “The 64th bit of Ω is 1.”

(This assumes that the FAS only enables you

to prove such theorems if they are true.)

这是一个极强的不完备性（incompleteness）结果，这是我所能做的最好的结果，因为它说，从本质上讲，确定Ω之比特的唯一方法就是把这些信息直接放到我们的FAS公理中，而根本不使用任何推理，可以说，只是通过查表来确定这些有限的比特集。

换句话说，Ω 的比特在逻辑上是不可还原的，它们无法从比它们更简单的公理中获得。最后 我们找到了模拟独立掷出一枚公平硬币的方法，我们找到了 "原子 "数学事实，这是一系列彼此毫无关联的无限数学事实，可以说，它们是 "无理由真"（没有比它们更简单的理由）。

而且，这个结果可以非正式地解释为：数学是随机的，或者更准确地说，数学包含随机性，即 Ω 之比特！不过，我们还需要注意一些严肃的问题！

数学并不是任意的，完全不是——2 +2 偶尔等于 5 而不是 4 ——绝对不是这种情况！但是，数学确实包含不可还原的信息，Ω 就是其中最典型的例子。

说 Ω 是随机的，可能有点令人困惑。它是一个特定的、确定的实数，从技术上讲，它符合我所说的 "随机实数"的定义。但是，数学常常以陌生的方式使用熟悉的词汇。也许更好的说法是，Ω 在算法上是不可压缩的。实际上，我更喜欢 "不可还原（irreducible）"这个词——虽然由于历史原因，"随机"这个词不可避免，但——我越来越多地使用它。

因此，也许最好的办法是避免误解，说Ω是不可还原的，这在算法或计算上是正确的，在逻辑上也是正确的，可以通过证明。而这恰好意味着Ω具有随机过程典型结果的许多特征，在物理意义上，随机过程是一个不可预测的过程，可以进行统计处理。

例如，正如我们将在下一节讨论的，在二进制中，在 Q. 的无限二进制展开中，2k 个可能的 k 位块（k-bit blocks）中，每一个都会以恰好 1/2k 的极限相对频率出现，这对于具体的实数 Ω 来说是可以证明的，尽管对于无限次独立抛掷一枚公平硬币的结果来说，这只是概率一，而不是确定无疑的。因此，回过头来看，也许选择 "随机 "这个词并没有那么糟糕！

另外，随机实数可能是无意义的，也可能是极有意义的；我的理论无法区分这两种可能性，也就无从谈起。如果这个实数是用一枚公平的硬币独立掷出每个比特的，那么它将是不可还原的，它将是无意义的。另一方面，Ω 是一个有很多含义的随机实数，因为它包含了很多关于停止问题的信息，这些信息以不可还原的方式存储在 Ω 中，没有冗余。你看，一旦你把任何有意义的东西中的冗余都压缩掉，结果必然看起来毫无意义，尽管它并非如此，根本不是这般，它只是充满了意义（meaning）！

再谈波莱尔正规数

事实上，我们不难发现Ω是正规的，也就是说，对于任何基数 b ，都是 b 正规的，而不仅仅是 2 正规（b-normal for any base b, not just 2-normal）。这一点的可爱之处在于，Ω 作为停止概率的定义似乎与正规性无关。Ω的构造并没有特别考虑到正规性；可以说，正规性就这么自由地出现了！

因此，对于任意基数 b 和任意固定基数 b "位数（digits）"k，Q. 之 b-ary 展开中，每 bk 个可能的 k 位数（k-digit）序列，其极限相对频率正好是 1/bk。在极限情况下，它们出现的可能性是相同的……

So for any base b and any fixed number k of base-b“digits,” the limiting relative frequency of each of the bk possible k-digit sequences in Q.‘s b-ary expansion will be exactly 1/bk. In the limit, they are all equally likely to appear …

如何证明情况一定是这样呢？好吧，如果不是这样，那么Q.的比特就会被高度压缩，被一个固定的乘法因子压缩，而这个乘法因子取决于相对频率的不等。换言之，Ω 的比特可以按固定的百分比压缩，这是一个很大的压缩量......这些想法可以追溯到克劳德-香农（Claude Shannon）于 20 世纪 40 年代在《贝尔系统技术期刊》（The Bell System Technical Journal）上发表的一篇著名论文，尽管我们工作的环境与他的论文有很大不同。不管怎么说，我就是通过阅读香农的文章获得了这个想法。香农和我都在工业实验室工作过：他的实验室是电话公司的，而我的实验室是 IBM 的。

我就是这样成功地找到了一个正规数！这是因为我对正规性本身并不感兴趣，而是对更深层次的哲学问题感兴趣，而正规性只是这些想法的一个应用而已。这有点类似图灵证明超越数（transcendentals）的存在，因为所有代数数（algebraic numbers）都必须是可计算的......

那么，城市学院教授理查德-斯通哈姆又是如何成功探索随机性的呢？这就是斯通哈姆的可证2正规数（prov-ably 2-normal number:）：

1 1 1

───＋───＋─── ↓

(3 × 2³) (3² × 2³²) (3³ × 2³³)

1

＋...────＋... ←

(3ᵏ × 2³ᵏ)

对于所有大小的区块，这都是正规基 2（normal base 2）。

那么，戴维-贝利和理查德-克兰德尔在 2003 年得到的更普遍的结果是什么呢？

1 1 1

───＋───＋─── ↓

(c × bᶜ) (c² × bᶜ²) (c³ × bᶜ³)

1

＋...────＋... ←

(cᵏ × bᶜᵏ)

只要 b 大于 1 且 b 和 c 没有公因数，就是 b 正规数。例如，b =5 和 c =7 就可以；这样就得到一个 5 的正规数。详情请参阅 Borwein 和 Bailey 合著的《实验数学（Mathematics by Experiment）》中关于正规数的第四章。书中还有很多其他有趣的内容，例如，计算 Π 的惊人新方法——实际上恰好与这些正规性证明有关！(见第三章）。

用二元方程求Ω的比特

在第五章中，我表达了对实数的数学怀疑论。在第四章中，我表达了对实数的物理怀疑。那么，我们为什么要认真对待实数 Ω 呢？因为它不是普通的实数，你可以通过二阶方程得到它！事实上，你可以用两种截然不同的方法得到它。

一种方法是我在 1987 年发现的，它可以模仿 Ω 的比特，让方程的解数从有限跳到无限。另一种方法是澳大利亚的托比-奥德（Toby Ord）和田德-基尤（Tien D. Kieu）在 2003 年发现的，它可以模仿 Ω 的比特，让方程的解数从偶数跳到奇数。这个问题有北半球和南半球的解决方法——毫无疑问，还有许多其他有趣的方法！

还记得克罗内克的信条吗？"上帝创造了整数，其他都是人类的杰作"。如果你愿意，Ω 根本不是一个实数，它是关于某些二叉方程的事实；它只与整数、正整数有关！因此，你不能把停止概率 Ω 的比特乃不可还原的数学真理这一事实推卸掉，因为这可以被重新解释为关于二阶方程的陈述。

Chaitin (1987)：

Exponential Diophantine Equation #1

In this equation n is a parameter，and k，x， y，z， . . . are the unknowns：

L(n，k，x，y，z，...)＝R(n，k，x，y，z，...). It has infinitely many positive-integer solutions if the nth bit of Ω is a 1.

It has onlyfinitely many positive-integer solutions if the nth bit of Ω is a 0.

Ord，Kieu (2003)：

Exponential Diophantine Equation #2

In this equation n is a parameter，

and k，x，y，z，... are the unknowns：

L(n，k，x，y，z，...) ＝ R(n，k，x，y，z，...).

For any given value of the parameter n，it only has finitely many positive-integer solutions.

For each particular value of n：

the number of solutions of this equation will be odd if the nth bit of Ω is a 1，and

the number of solutions of this equation will be even if the nth bit of Ω is a 0.

如何构造这两个二元一次方程？嗯，细节有点乱。下面的方框给出了总体思路；它们总结了需要做的事情。正如你所看到的，我们之前讨论过的Ω近似值的可计算序列起着关键作用。同样重要的是，特别是对于 Ord 和 Kieu (2003)，要记住这些近似值是一个非递减的有理数序列，它们越来越接近 Ω，但始终小于 Ω 的值。

数学联邦政治世界观提示您：看后求收藏（笔尖小说网http://www.bjxsw.cc），接着再看更方便。