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

事实上，我们刚刚已经证明，如果我们的停止问题算法，其大小是N比特，那么一定有一个程序是永远不会停止的，而且这个程序的大小最多只是比N比特大几个比特，但我们不能用我们的N比特停止问题算法加以决定这个程序永远不会停止。(我们假设停止问题算法宁愿永远不给出答案，也不愿给出错误答案。这种算法可以重新解释为 FAS）。

因此，我们刚刚证明了图灵著名的 1936 结果，与他最初证明的方式完全不同，我们使用的是程序大小、算法信息和软件复杂度的概念。在我找到的所有图灵结果的证明中，这个是我最喜欢的。

现在我必须坦白另一件事。我认为，在找到自己的证明之前，你无法真正理解一个数学结果。读别人的证明不如自己找证明。事实上，我认识的一位优秀数学家罗伯特-索洛维从不让我向他解释证明。他总是坚持只让我告诉他结果的陈述，然后他自己去思考！我对此印象深刻！

这是我能找到的对图灵结果的最直接、最直接、最基本的证明。我试图抓住问题的核心，去掉所有杂乱无章的东西，去掉所有妨碍理解的外围细节。

这也意味着，我们在第二章讨论希尔伯特第10个问题时缺失的部分现在已经补上了。

为什么停止问题很有趣？嗯，因为在第二章中，我们证明了如果停止问题无法解决，那么希尔伯特第 10 个问题也就无法解决，也就没有算法来决定二叉方程是否有解。事实上，图灵的停止问题与希尔伯特的第 10 个问题是等价的，从这个意义上说，任何一个问题的解都会自动地提供（provide）/担保（entail）另一个问题的解。

停止概率Ω和自限制程序

现在，我们将真正获得不可还原的数学事实，即 "无理由真（are true for no reason）"的数学事实，它在纯数学中尽可能地模拟了公平硬币的独立抛掷：这是停止概率Ω之基二扩展（base-two expansion）的比特！你无法证明一个程序是优美的，这个美丽而富有启发性的事实只是一个热身练习！

与其像图灵那样只看一个程序，问它是否停止，不如把所有可能的程序装进袋子里，摇一摇，闭上眼睛，挑出一个程序。我们随机选择的这个程序最终停止的概率是多少？让我们用一个介于 0 和 1 之间的无限精确二进制实数来表示这个概率。瞧！它的位数就是我们独立的数学事实。

The Halting Probability Ω

You run a program chosen by chance on a fixed computer. Each time the computer requests the next bit of the program. flip a coin to generate it，using independent tosses of a fair coin The computer must decide by itself when to stop reading the program. This forces the program to be self-delimiting

binary information.

You sum for each program that halts

the probability of getting precisely

that program by chance：

Ω＝∑ program p halts 2—(size in bits of p)

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