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

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]的实数！）。

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