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

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

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