#Technomous #PL

图灵的哑谜

说到底，谕示是什么呢？我们来看看图灵在他的博士论文中的定义：

“假定我们拥有某种解决数论问题的未知方法；比如说某种谕示。我们不深入这个谕示的本质，除了它不可能是一台机器这一点。通过谕示的帮助，我们可以构筑一种新的机器（叫做o-机），它的基本过程之一就是解决某个给定的数论问题。”

在这里，图灵说的“数论问题”，其实是指描述自然数的一类特殊的逻辑命题，用现在的术语来说叫 ${\mathrm{\Pi }}_1^0$ 命题。“数论问题”只是图灵取的一个名字，与真正的数论研究关系不大。

图灵的这段文字其实定义了一种新的图灵机，图灵把它叫做“o-机”，而它的现代术语叫“谕示机”。一台谕示机就是一台有点特别的图灵机，仅仅多了一个新功能，就是能“免费”得到某一个特定的判定问题的答复。比如说，一个带有素数判定谕示的谕示机，除了能做普通图灵机能做的一切事情以外，还能瞬间判定纸带上写的某个自然数是否素数，而不需要实际去计算。

那么，是不是谕示机就一定比普通的图灵机强大呢？就像两位学生参加同一场范围不定的不限时开卷考试，他们的能力与掌握的知识相同，一位学生带了一本参考书，而另一位则什么资料都没带，带了书的那位是不是一定比另一位更有优势呢？

这就要看参考书到底是什么了。如果两位学生都懂参考书中的所有内容的话，那么参考书并不会带来什么优势，可能带书的学生会答得快一些，但既然考试不限时，没带书的学生多用点时间也总能答出来。但如果参考书是两位学生都没有见过的内容的话，带了书的学生自然略有优势。如果考试题目中包含了参考书中的一些内容，而两位学生本来都不懂的话，带了书的可以翻书回答，没带书的就只能干瞪眼了。

同样，在我们比较一台谕示机与一般的图灵机的能力时，也要看看谕示回答的具体问题是什么。如果谕示解决的问题本来就是可计算的话，一般的图灵机即使没有谕示，也能多花点时间把答案计算出来，这时谕示机毫无优势；但如果谕示能解决一个不可计算的问题，比如说停机问题的话，谕示机显然能解决同样的问题，而一般的图灵机则无法解决，因为问题本身是不可计算的，这时谕示机的能力显然比没有谕示的图灵机要强。

所以说，谕示机的力量蕴含在它拥有的谕示能回答的问题，而谕示机中谕示的具体问题可以是任意的。我们可以考虑带有停机问题谕示的谕示机，如果这台机器的纸带上写着一台普通图灵机的“代码”以及输入，那么它不需要计算就能可以瞬间知道，这台普通图灵机遇到指示的输入时到底会不会停机。所以，对于谕示机而言，它不受普通图灵机的可计算性的限制，能够“计算”超越机械计算本身极限的问题。当然，这也意味着，对于一个不可计算的问题，我们不可能实际地建造一台谕示机。

也就是说，谕示机这个概念，只是一个单纯的数学概念，仅仅用于数学上的探索，而不可能实实在在地出现在我们面前。图灵当然也意识到这一点，在他的论文中，也确切声明谕示机并不属于机械计算的范畴。也许这就是图灵使用“谕示”这个名字的原因。“谕示”的原文 oracle，来自拉丁语中的oraculum，从 orare 加上物化工具后缀-oculo 得到。orare 的意思是“祈求”或者“祷告”，而 oracle 的意思就是“神的宣布”，也就是神谕。图灵是一位无神论者，他相信神是不存在的，所以神谕当然也不存在。用它来命名一台不可能实现的机器，实在是再适合不过了。

Duerer-Prayer, from Wikipedia

那么，在论文中图灵用谕示机证明了什么呢？

图灵考虑的是一类特殊的谕示机，其中的谕示能回答一切“数论问题”，也就是说，这个谕示能判断任意的“数论问题”是否为真。但除此之外，它就是一台普通的图灵机，于是我们也能考虑关于它的停机问题：给定一台这样的谕示机的代码（不包含谕示本身），以及一个输入，这台谕示机在这个输入上会不会停机呢？

对于普通的图灵机而言，停机问题是不可判定的，这早已被证明。而图灵发现，即使将证明中的所有“图灵机”三个字都换成“带有‘数论问题’谕示的谕示机”，其他部分一字不易，证明依然成立！也就是说，就像普通图灵机不能解决关于自身的停机问题，谕示机也不能解决关于自身的停机问题，无论它的谕示有多么强大。

所以，图灵的结论是，存在带有“数论问题”谕示的谕示机也不能解决的问题，但既然这种谕示机能解决所有“数论问题”，所以不能归结为“数论问题”形式的数学问题是存在的。

这个结论，未免大材小用。不需引入谕示机，以图灵的才智，也有办法证明相同的结论。在整篇论文中，谕示机这个概念只出现在第四章，专门用于探讨“数论问题”的局限性，而这一章基本与论文全体独立，即使删去也不影响结论。用不必要的工具，证明了不必要的结论，图灵到底在想什么，其中是否别有深意？为什么要加上这一章？这些问题的答案，只有图灵自己知道。

幸而，仅仅 5 年后的 1944 年，就有人破解了谕示机的哑谜。

谕示机的谕示

让我们回到开卷考试的比喻。在日常生活中，范围不定的考试毕竟少见，多数考试的范围都是相对明确的某个科目，比如说高考语文、数学分析、考研英语、公务员考试中的申论等等。我们经常说，某某省的高考数学难度比某某省的要大，或者高等数学比数学分析要简单。那么，当我们说“某门科目的考试比另一门简单”的时候，我们到底在说什么？

我们尝试一下用数学家的思路来解决问题。

首先，我们希望比较不同的科目，给它们排个顺序。我们潜意识认为，每个科目都有它固有的难度。如果科目 A 比科目 B 要难，科目 B 比科目 C 要难，那么科目 A 比科目 C 要难。也就是说，这种顺序是有“传递性”的。于是，从数学的角度来看，我们要考察的是不同的考试之间的所谓“序关系”，也就是说它们之间两两的难度顺序关系。

其次，我们也发现并不是所有的科目都能相互比较。比如说高考理科数学和对外汉语，高三理科生对前者可能驾轻就熟，但对后者大概一筹莫展；而对外汉语专业的大学生可能恰好相反。所以，科目之间的难度不是一个绝对的数字，有些科目之间不能比较。这与日常生活中的“顺序”关系很不相同，比如说日期或者温度，总有个前后高低之分，不会有两个不能比较的日期或者温度。像日期和温度这类总能比较两个元素的序关系，在数学上被称为“全序关系”；像考试科目这类不一定能比较任意两个元素的序关系，则被称为“偏序关系”。这里的“偏”跟“以偏概全”中的意思差不多，指的是“不全面”。

Partial ordering of the sciences, from Wikipedia

现在我们知道，我们要寻找的其实是考试科目之间的偏序关系。那么，给定两个考试科目，有什么办法能分辨两者孰难孰易，又或者无法比较呢？

有一些科目之间是很容易比较的，比如说小学数学当然比中学数学要容易，这是因为中学数学包含了小学数学的内容。一名能完成中学数学考试的学生，必定能完成小学数学考试。但有一些科目就不那么好比较了。线性代数和简单电路计算，初看风马牛不相及，一个是数学一个是物理，似乎没法比较。一个会线性代数的学生，如果没学过电路，似乎也没有理由能进行电路的计算。但如果这位学生知道基尔霍夫定理的话，他就能将电路计算的问题转化为线性方程组，从而用线性代数的知识去解决电路计算的问题。从这一点上来看，似乎电路计算要比线性代数容易，因为存在一种机械而固定的方法（电路的基尔霍夫定理），将电路计算的问题转化为线性代数的问题，而线性代数的问题则不一定能表达成电路的形式来求解。

把这种直觉抽象成数学语言的话，如果对于两门科目 A 和 B，存在一种简单的方法 P，能将科目 A 中的任意问题转化为科目 B 中的问题的话，那么 B 就不比 A 更简单，因为如果我们能解决科目 B 中的问题，那么面对科目 A 中的一个问题，我们只需要先用 P 将这个问题转化到我们能解决的科目 B 中，再用我们的知识去解决转化后的问题，那么就相当于间接解决了科目 A 中的原问题。如果这种转化是双向的，也就是说如果存在另一种方法能将科目 B 中的任意问题转化为科目 A 中的问题，那么我们就说 A 与 B 难度相当，否则我们就说 B 比 A 难。

这种将一个领域的问题变换到另一个领域来处理的方法，在数学中被称为化归或者规约（reduction），是数学家们常用的手段。将组合计数问题化归成连续函数的计算与展开，将代数方程的解空间化归成连续流形，不同的化归手法被数学家们源源不断地创造出来，一开始是神来之笔，但经过几代数学家的努力，最后积淀下来的就是一门全新的数学分支。通过规约，数学家能借用不同领域的各种工具来解决千变万化的各种问题。可以说，对于规约这一门手段，数学家们是再熟悉不过了。但将“规约法”本身抽象出来，则需要真正的数学洞见。

也许是因为太熟悉太习以为常，几乎没有人想到，规约法暗含着计算的另一重含义。

回到考试科目的比喻。如果有两门科目 A 与 B，它们非常非常难，没有学生能不靠课本完成考卷里的任何一道题目，但只要有相应的课本，那么要拿到满分也不是特别困难。虽然两门科目都很难，但大家一般也认为 B 比 A 要更难一些。幸而这两门考试都是开卷，所以也没有人抱怨。有一天，一位学生急匆匆跑到科目 A 的考场，打开书包一看，才发现课本拿错了，手上只有科目 B 的课本。怎么办？

一般来说，开卷考试带错课本基本上就是死路一条。但我们知道科目 A 比科目 B 要容易，也就是说，存在一种方法，可以将科目 A 的问题转化为科目 B 的问题。那么，既然有科目 B 的课本，那么如果这位学生同时也知道问题转化的方法，那么先将试卷上的问题转化为科目 B 的问题，然后参考科目 B 的教科书解决这些问题，根据对应问题的答案，自然就能完美完成科目 A 的考试。

而谕示机，实际上就是一名带着课本参加开卷考试的学生。

判定问题即是考试科目，课本即是谕示，而学生本人，则是带有程序的图灵机。而我们比较考试科目相对难度的方法，实际上就是比较判定问题相对难度的方法。

我们知道，一台谕示机其实就是一台图灵机加上一个能解决某个特定判定问题的“谕示”。假设我们有两个特定的判定问题 A 与 B，而我们希望比较两个问题的“难度”。对于判定问题 A，我们将记载了 A 的所有解答的谕示称为谕示 A。那么，我们考虑那些带有谕示 A 的谕示机，它们都能很快解答 A 的任意实例。如果存在一台这样的谕示机，它总能正确解答判定问题 B 的话，那么我们就说问题 A 至少比问题 B 要难。这跟开卷考试一样，不能奢求每位学生都知道怎么将科目 B 的问题转化到科目 A 中，但只要有一名学生知道怎么做，那么这种转化的方法就存在。在这种情况下，我们说问题 B 能够“图灵规约”到问题 A，可以记作( B ${\le }_T$ A )；如果同时问题 A 也能图灵规约到问题 B 的话，我们就说 A 与 B 是“图灵等价”的。

通过图灵规约与谕示机，我们可以比较不同的判定问题之间的相对难度。但谕示机本身就是一种计算方法，它从一个已知的问题出发，通过谕示假定这个问题已经被解决，从而探索那些相对于已知问题而言可以计算的问题。带有某个特定谕示的谕示机，它们能进行的计算是相对于某一个特定问题而言的。某个问题能否计算，取决于我们手上的谕示，换句话说，我们手上已有的知识。

作为一个概念，可计算性是相对的，而不是绝对的，这就是谕示机带给我们的谕示，也许也是图灵论文中哑谜的答案。

那么，揭示出这个谕示的，到底是怎么样的人呢？