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

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公理中，而根本不使用任何推理，可以说，只是通过查表来确定这些有限的比特集。

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

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