元数学：计算机、悖论与数学基础 (8-4)

图灵的原始论文包含了一种编程语言，就像哥德尔的论文一样，也就是我们现在所说的编程语言。但这两种编程语言截然不同。图灵的编程语言并非像 LISP 这样的高级语言；它更像是一种机器语言，是输入计算机中央处理器的 1 和 0 的原始代码。事实上，图灵在 1936 年的发明，是一种糟透的机器语言，今天没有人会想用它，因为它太初级，太不成熟了。

尽管图灵所假想的计算机非常简单，其机器语言亦颇为原始，但它们却非常灵活。图灵在 1936 年的论文中声称，这样的机器应该能够完成人类所能够完成的任何计算。

图灵的思路，现在发生了戏剧性的转变。他问，对于这样一台机器来说，有什么是不可能的？它不能做什么？他立刻发现了一个图灵机所无法解决的问题：停止问题（the halting problem）。这是一个对图灵机（或计算机程序）最终是否会找到其想要的解并停止加以提前决定的问题。

halt

l →

K → H →lop？→ ◯

→ F ↺

倘若允许时间限制，这个问题就很容易解决。假设你想知道一个程序是否会在一年内停止运行。那你就运行它一年，它要么停止，要么不停止。图灵所证明的是，如果你并不设时间限制，如果你试图在并不对程序加以运行的情况下，推断程序是否会停止，你就会遇到大麻烦。

让我来概述一下图灵的推理： 假设你可以编写一个计算机程序，对任何给定的计算机程序最终是否会停止加以检查。称之为终止测试器（termination tester）。理论上，你给它输入一个程序，它就会吐出一个答案： "是的，这个程序会终止"，或者，"不，它会在某个无限循环中转个不停，永远不会停止"。现在创建第二个程序，该程序对终止测试器加以动用，来评估某个程序。如果正在调查中的程序终止了，那么你的新程序就会被安排进一个无限循环。精妙的部分来了： 给你的新程序输入一个其自身之副本。它会做什么？

记住，你所编写这个新程序，其目的是，如果被测程序终止，那么新程序将进入无限循环。但在这里，它本身就是被测程序。因此，如果它终止，就会进入无限循环，这意味着它不会终止——这是一个矛盾。对相反的结果加以假设同样无济于事： 如果程序没有终止，终止测试器就会指出这一点，程序就并不会进入无限循环，从而终止。这个悖论让图灵得出结论：无法设计出通用的终止测试器。

有趣的是，图灵立即推导出一个推论： 如果无法通过计算以对一个程序是否会停止加以预判，那么也就无法通过推理来对程序是否会停止加以预判。没有任何一个形式化的公理系统，能让你推导出，程序最终是否会停止。为什么呢？因为如果你能以这种方式对形式公理系统加以使用，那你就有办法事先计算出，程序是否会停止。而这是不可能的，因为你会陷入一个悖论。比如 "这句话是错的！" 你可以创建一个当且仅当它不停止时，才会停止的程序。这个悖论与哥德尔在研究数论时所发现的情况类似。(回想一下，他当时研究的只是 0、1、2、3......以及加法和乘法，并没有更复杂的东西）。图灵的绝招在于，他证明了任何形式公理系统都不可能是完备的。

二战爆发后，图灵开始研究密码学，冯-诺依曼开始研究如何计算原子弹爆炸，人们暂时忘记了形式公理系统的不完备性。

数学中的随机性

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