7.1　骗子悖论

请考虑如下这个令人困惑的命题。

图7-2　方框中的命题：这个命题不是真的

这个命题是真是假？如果它是假的，那么它不能不是真的，双重否定意味着它是真的。如果这个命题是真的，那么如其所说，它不是真的而是假的。两种假设，都会导致矛盾。这个悖论经常被称为骗子悖论。我现在正在撒谎。你觉得呢？

良好的数学系统中是不允许出现正确的悖论的，悖论的存在说明数学系统不够好。“这个命题不是真的”是不可被数学规范化的，因为一个命题不能讨论它本身的真伪。

20世纪30年代，库尔特·哥德尔发现了数学可以讨论证明的真伪，他可以构造一些数学命题，来表明其他的命题是否存在能证明其正确性的证据。哥德尔发现了如何让一个命题讨论它本身正确性的证明是否存在的方法，并建立了一个与上面类似的数学公式：

图7-3　方框中的证据：没有证据表明这个命题是真的

假设这个命题为假，那么有证据表明这个命题是真的，这和它为假的假设矛盾，所以这个命题必须是真的。

我们又遇到悖论了吗？不完全是。这个命题是真的，然而没有证据表明它是真的。哥德尔看似轻描淡写的一击，却撼动了数学大厦的基础：存在人们不能证明其为真的真命题。¹

_{1 我们刚才没有证明那个命题是真的吗？不完全如此，因为不得不首先假设所有能被证明为真的命题都确实是真的。于是哥德尔同时也表明了，我们不能证明“所有能被证明为真的命题都确实是真的”，除非我们能证明假的命题。这就是你读脚注的好处。}

如果有人告诉你他有一个能预测未来的魔盒。你就问他你会用右手打他还是用左手。如果盒子说左手，你就用右手打那个人。如果盒子说右手，你就用左手。不管怎样盒子都是错的。

计算也同样可以这样。我们都见过计算机屏幕上出现一个代表忙碌的小沙漏，不知道这是代表计算机死机了，还是在进行长时间的计算。用户该马上重启机器呢，还是再等一会儿？如果能有一个算法，告诉我们计算机是不是陷进了某种无穷循环该多好！那是很好，但那也是不可能的。

为理解其中的道理，我们先来看一下1936年阿兰·图灵在开创计算机科学的论文中给出的一个例子。计算机程序也是数据，就像文档和报表一样。程序可以分析程序的代码。

一个计算机程序要么最终结束计算并输出结果，要么永远算下去。假设我们有一个算法，它能告诉我们某个程序是否会最终结束。我们把这个程序对它本身运行一下。

图7-4　方框中的程序：如果这个方框中的程序结束，那么它会永远运行下去

这个方框中的程序要么会结束，要么不会结束。不管怎样，我们都遇到了矛盾。所以我们的假设是错误的，即不存在一个程序，能告诉我们某个程序能否最终结束。PC上没有，Mac上也没有。现在没有，100年后也不会有。不存在一个程序能告诉我们某个程序能否最终结束，就这么简单。

我们能用类似的思路来证明人们无法高效地解决某些问题，也就是证明该问题不属于类型P（即我们能高效解决的问题）吗？这确实是可行的。

我们先构造一个算法Q，将一段程序R的代码作为其输入数据，它的工作原理如下：

• 如果程序R在使用R的代码作为数据时能很快输出“Yes”，那么Q输出“No”；
• 否则Q输出“Yes”。

假设算法S是一个高效的算法。那么，Q(S)当且仅当S(S)输出“No”的时候输出“Yes”。所以不存在行为与Q完全相同的高效算法。

Q仍然是一个符合规范的算法。所以Q所解决的这个问题是可被计算的，但不能被高效地计算。

如果我们能证明Q在NP中，也就是说，可以高效地验证其解的有效性，那么Q在NP中，而不在P中。这意味着P≠NP，从而解决了那个伟大的问题。

但是我们不知道，而且通常不认为，存在一个关于Q的NP算法。由于这个原因以及其他的某些原因，这条试图以悖论来解决P/NP问题的道路注定会通向失败，至少它不能直接用来证明P≠NP。