重温图灵原理，感受反证法的力量

算法已经变得无处不在，似乎对于每一个可以用精确数学术语表达的问题，都有一种对应的算法。但事实并非如此，其实一些看似简单的问题永远无法用算法解决。

计算机科学家中的先驱艾伦・图灵，曾在近一个世纪前的一篇论文中证明了这种「不可计算」问题的存在，他提出了启动现代计算机科学的计算数学模型。

图灵用一种违反直觉的策略证明了这一突破性的结果：他定义了一个问题，一个拒绝一切试图解决它的方法的问题。「比如我问你在做什么，不管你回答什么我都会说，‘我要做的事情和你说的不一样’。」麻省理工学院研究理论计算机科学的研究生 Rahul Ilango 说。

图灵的策略是基于一种有着悠久璀璨历史的、被称为「对角线证明」的数学方法。以下是他证明背后逻辑的简化说明。

字符串

对角线证明源于解决一个关于字符串问题的巧妙技巧，字符串中每个比特位的值可以是 0 或 1。该问题的描述是：给定一个字符串列表，列表中所有字符串都一样长，如何能生成一个不在列表中的新字符串呢？

最直接的策略是依次考虑每个可能的字符串。假设有五个字符串，每个字符串有五位长。首先遍历检查列表中是否存在 00000。如果它不存在，问题解决；如果存在，则转到 00001 并重复该过程。这很简单，但对于长字符串所产生的长列表来说速度很慢。

对角线证明是一种可行的替代方法，可以一点一点地构建不存在的字符串。从列表中第一个字符串的第一位开始，将其反转 —— 这将是新字符串的第一个位。然后反转第二个字符串的第二个位，并将其用作新字符串的第二位，重复此操作，直到到达列表的末尾。翻转位的操作能确保新字符串与原始列表中的每个字符串至少有一处不同。（它们还在字符串列表中形成一条对角线，从而为该算法命名。）

对角线证明只需要依次检查列表中每个字符串中的一位，所以通常比其他方法快得多，但它真正的威力在于它能很好地驾驭无限长的字符串问题。

麻省理工学院的理论计算机科学家 Ryan Williams 说：「字符串现在可以是无限的，列表也可以是无穷的，但对角化方法仍然有效。」

Georg Cantor 是第一个利用这种力量的人，他是集合论数学子领域的创始人。1873 年，他用对角线证明了一些无穷大的值比其他的更大。60 年后，图灵将这一版本的对角线证明应用于计算理论。

算法的局限性

图灵想证明存在任何算法都无法解决的数学问题，也就是说，有明确定义的输入和输出，但没有从输入到输出完全确定的过程的问题。图灵只关注决策问题，为了使这项模糊的任务更易于具象化。在决策问题中，输入是 0 和 1 组成的任何字符串，输出可以是 0 或 1。

确定一个数字是否是素数（只能被 1 和它本身整除）是决策问题的一个例子 —— 给定一个代表数字的输入字符串，如果该数字是素数，则正确的输出为 1，如果不是素数，则为 0。另一个例子是检查计算机程序的语法错误。输入字符串代表不同程序的代码 —— 所有程序都可以用这种方式表示，因为这就是它们在计算机上存储和执行的方式 —— 规则是如果代码包含语法错误，则输出 1，如果不包含，则输出 0。

只有当算法为每一个可能的输入都产生正确的输出时，它才能说是可以解决该问题 —— 哪怕失败一次，它就不是解决该问题的通用算法。通常，人们会先指定一个想解决的问题，然后试图找到一个解决它的算法。图灵在寻找无法解决的问题时，颠覆了这一逻辑 —— 他想象了一个包含所有可能算法的无限列表，并使用对角化来构造一个难题，这个难题与列表上的每一个算法都对立。

想象一下，一个由 20 个问题组成的新问题，回答者不是从一个具象的概念出发，而是依次对每一个问题都想出一个不满足的例子。到游戏结束时，回答者已经描述了一个完全由问题对立面所组成的命题。

图灵的对角线证明过程，就是要在无限长的算法列表中，对每一个算法都进行思考：「这个算法能解决我们想要证明是不可计算的问题吗？」，就好像是一种游戏比赛。Williams 表示：「这种方式将原来的问题转化为一种『无限的问题』。」

为了赢得游戏，图灵需要设计一个问题，对于每个算法给出的答案都是否定的。这意味着需要找出使第一个算法输出错误答案的特定输入，另一个使第二个算法失败的输入，以此类推。他发现，这些特殊输入使用了类似于库尔特・哥德尔 (Kurt Gödel) 在不久前在证明像「这个命题是不可证明的」这样的自我引用断言会给数学基础带来麻烦时，所使用的技巧。

此处的关键在于，每个算法（或程序）都可以表示为 0 和 1 的字符串。这意味着，就像在错误检查程序的例子中一样，算法可以将另一个算法的编码作为输入。原则上，算法甚至可以将自己的编码作为输入。

如此一来，我们可以定义一个不可计算的问题，就像图灵证明中的问题一样：「给定一个表示算法代码的输入字符串，当算法自身的代码是输入时，如果该算法输出 0，则令其输出 1，否则输出 0。」每个试图解决这个问题的算法都会在至少一个输入上产生错误的输出 —— 即与自己的代码对应的输入。这意味着这个反常的问题不能用任何算法来解决。

反证法证明不了什么

计算机科学家对于对角线证明的使用并没有到此结束。1965 年，Juris Hartmanis 和 Richard Stearns 改编了图灵的论点，以证明并非所有可计算问题是平等的 —— 有些问题本质上比其他问题更难。这一结果启动了计算复杂性理论领域，研究计算问题的难度。

但复杂性理论也揭示了图灵对角线证明的局限性。1975 年，Theodore Baker、John Gill 和 Robert Solovay 证明了复杂性理论中的许多开放问题永远不能仅靠对角化来解决。其中最主要的是著名的 P/NP 问题，该问题简单来说就是能在多项式时间内验证某个解是否正确的问题，是否能在多项式时间内求解。

对角线证明的局限性是使其如此强大的高抽象水平的直接结果。图灵的证明并没有涉及任何在实践中可能出现的不可计算的问题 —— 相反，问题往往是抽象的。其他对角线证明同样远离现实世界，因此它们无法解决现实世界中的问题。

Williams 说：「对角线证明并不是直接触碰问题本身，就好像用手套箱做实验一样。」

对角线证明的颓败之势，表明解决 P/NP 问题将是一个漫长的旅程。尽管存在局限性，对角线证明仍然是复杂性理论家武器库中的关键工具之一。2011 年，威廉姆斯将其与一系列其他技术结合起来，证明了某个受限制的计算模型无法解决一些异常困难的问题 —— 这一结果让困扰了研究人员 25 年的问题得到解决。虽然这与解决 P/NP 问题相去甚远，但仍然代表着重大进展。

如果你想证明有些事情是不可能的，不要低估说「不」（反证法）的力量。

原文链接：

https://www.quantamagazine.org/alan-turing-and-the-power-of-negative-thinking-20230905/