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

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

换句话说，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）：

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

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