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

Chaitin (1987)：

Exponential Diophantine Equation #1

Program(n，k) calculates the kth approximation to Ω，in the manner explained in a previous section.Then Program(n，k) looks at the nth bit of this approximate value for Ω.If this bit is a 1，then Program(n，k) immediately halts；otherwise it loops forever.

So Program(n，k) halts if and only if

(the nth bit in the kth approximation to Ω) is a 1.

As k gets larger and larger，the nth bit of the kth approximation to Ω will eventually settle down to the correct value. Therefore for all

sufficiently large k：

Program(n，k) will halt if the nth bit of Ω is a 1.

and Program(n，k) will fail to halt if the nth bit of Ω is a 0.

Using all the work on Hilbert’s 10th problem that we explained in Chapter Two，we immediately get an exponential diophantine

equation

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

that has exactly one positive-integer solution if Program(n，k)eventually halts，

and that has no positive-integer solution if Program(n，k) never halts.

Therefore，fixing n and considering k to be an unknown，this exact same equation

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

has infinitely many solutions if the nth bit of Ω is a 1，

and it has only finitely many solutions if the nth bit of Ω is a 0.

Ord，Kieu (2003)：

Exponential Diophantine Equation #2

Program(n，k) halts if and only if k＞0 and

2"×(jth approximation to Ω) ＞ k

for some j＝1，2，3，...

So Program(n，k) halts if and only if 2"×Ω ＞ k ＞ 0.

Using all the work on Hilbert’s 10th problem that we explained in Chapter Two，we immediately get an exponential diophantine

equation

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

that has exactly one positive-integer solution if Program(n，k) eventually halts，

and that has no positive-integer solution if Program(n，k) never halts.

Let’s fix n and ask for which k does this equation have a solution.

Answer：L(n，k) ＝ R(n，k) is solvable precisely for k＝1，2，3，...， up to the integer part of 2"× Ω.

Therefore，L(n) ＝ R(n) has exactly integer part of 2"× Ω solutions，which is the integer you get by shifting the binary expansion for Ω left n bits. And the right-most bit of the integer part of 2"× Ω will be the nth bit of Ω.

Therefore，fixing n and considering k to be an unknown，this exact same equation

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

has an odd number of solutions if the nth bit of Ω is a 1，and it has an even number of solutions if the nth bit of Ω is a 0.

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

这里是讨论一个重要问题的好地方。在上一章中，我们指出实数在算法上不可还原的概率为 1。算法上可压缩的实数概率为零。那么，为什么对随机实数 Ω 有兴趣呢？当然有很多随机实数！

原因有很多。

首先，Ω将我们与图灵的著名结果联系起来；停止问题是不可解的，而停止概率是随机的！一种情况是算法上的不可解，另一种情况是算法上的随机性或不可压缩性。此外，Ω 的前 N 位还为我们提供了许多关于停止问题的特殊、个别情况的信息。

不过，Ω之所以有趣，主要原因在于此： 我们在无限黑暗的随机实数中，挑选出了一个随机实数！我不敢说我们能触摸到它，但我们肯定能直指它。而重要的是，通过展示一个具体的例子，让这种模糊变得有形。毕竟，如果我们不能展示具有某种属性的具体事物，我们为什么要相信大多数事物都具有这种属性呢？

(不过，请注意，对于同样概率为 1 的不可名状的实数，我们永远也不可能找出一个单独的不可名状[un-nameable]的实数！）。

这里还有另一种说法： Ω在很大程度上是不可计算的，但它看起来几乎是可计算的。它跨越了我们所能处理的事物同超越我们数学家能力的事物之间的边界。因此，它的作用是建立一个清晰的边界，在沙地上划出一条我们不敢逾越、不能逾越的细线！

这也与，我们可以计算出越来越好的Ω下界（ lower bounds）这一事实有关，只是我们永远无法知道我们已经接近了多少。

换句话说，要让不完备性结果真正令人震惊，情况必须是，正当我们要伸出手去触摸什么的时候，我们的手指却被打了一巴掌。我们永远也吃不到它了，即使它就摆在餐桌上，旁边还有很多其他诱人的食物！这比我们被告知不能拥有某样东西或做某件事更让人沮丧，也更有趣，因为我们从来没有被告知不能拥有某样东西或做某件事，这似乎不够具体，也不够脚踏实地，从一开始就不像是一种合理的可能性！

故事的寓意是什么？

因此，数学真理的世界具有无限的复杂度，尽管任何给定的 FAS 都只有有限的复杂度。事实上，即使是二叉问题的世界也具有无限的复杂度，任何有限的 FAS 都无法做到这一点。

因此，我认为我们不能像希尔伯特所希望的那样，坚持使用单一的 FAS，我们必须在理论基础上不断添加新的公理、新的推理规则或其他新的数学信息。那么，我们从哪里可以得到那些无法从我们已经知道的东西中推导出来的新东西呢？嗯，我不确定，但我认为它可能来自物理学家获得新方程的相同地方：基于灵感、想象力和——就数学而言——计算机，而不是实验室——实验。

拉卡托斯在托马斯-泰莫茨科（Thomas Tymoczko）的有趣文集《数学哲学的新方向》（New Directions in the Philosophy of Mathematics）中的一篇文章中创造了这个术语。这与所谓的 "实验数学 "思想密切相关，后者利用计算证据而非传统证明来 "确立 "新的真理。博尔文、贝利和吉尔根森在两卷本著作中论证了这种研究方法的好处，他们认为，这种方法不仅有时极其方便，而且事实上有时甚至是绝对必要的，这样数学才能在不完备性现象中取得进步......

好了，这就是我的不完备性研究方法，它与哥德尔和图灵的方法截然不同。它的主要思想是用生成所有定理的最小程序的比特大小加以衡量FAS之复杂度或信息含量。一旦做到这一点，其他一切都会水到渠成。从最初的洞察力出发，事情或多或少都会变得简单明了，发展也或多或少都会变得系统化。

是的，但正如波利亚（Pólya）尖锐地问道："你能一目了然吗？" 是的，事实上我认为我们可以：

任何机械的过程（游戏规则）都不可能真正具有创造性，因为从某种意义上说，任何东西的产生都已经包含在你的起点之中。这是否意味着，物理随机性、掷硬币等非机械性的东西，是创造力的唯一可能来源？至少从这个（过于简单化的）角度来看，是这样的。

反对利己主义

思想史给我们带来了许多惊喜。在本书中，我们已经看到了这一点：

数字哲学可以追溯到莱布尼兹 数字物理学可以追溯到芝诺

我通过复杂性对随机性的定义可以追溯到莱布尼茨。

我的Ω数可以追溯到波莱尔的全知实数。波莱尔数也是图灵后来称之为不可计算实数的一个例子。

我关于无法证明程序是否优美的证明，其主要思想——事实上，这也是我所有不完备性结果的基本思想——可以追溯到波莱尔的随机性不可定义悖论。

我认为，这些看法应该成为一种解毒剂，以防止过度的利己主义、竞争和愚蠢的优先权之争毒害科学。任何科学思想都不可能只有一个名字；它们是人类最优秀思想的共同结晶，在历史长河中相互借鉴。

这些思想可以追溯到那么久远的年代，那么长的线索，但这丝毫不会削弱它们。相反，这赋予了它们更大的意义。

我的朋友雅各布-T-施瓦茨（Jacob T. Schwartz）曾告诉我，中世纪的大教堂是许多无名之辈用毕生精力建造而成的。施瓦茨乐于引用当时一位著名医生的话，他在谈到一位病人时说："我给他以治疗，而上帝则给他以治愈！" 我认为，在科学和数学领域，这也是一种正确的态度。

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