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

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

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

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

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

字符串

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

重写后的内容：一种最直接的策略是按顺序考虑每个可能的字符串。假设有五个字符串，每个字符串都有五位。首先遍历检查列表中是否存在00000。如果不存在，问题就解决了；如果存在，则转到00001并重复这个过程。这种方法很简单，但对于长字符串所产生的长列表来说速度很慢

对角线证明是一种可行的替代方法，可以逐步构建不存在的字符串。从列表中第一个字符串的第一位开始，将其反转，这将成为新字符串的第一位。然后反转第二个字符串的第二位，并将其作为新字符串的第二位，重复此操作，直到到达列表的末尾。通过反转位的操作，可以确保新字符串与原始列表中的每个字符串至少有一个不同的位置。（它们还在字符串列表中形成一条对角线，因此被称为对角线证明。）

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

麻省理工学院的理论计算机科学家 Ryan Williams 表示：“虽然字符串和列表可以是无限的，但对角化方法仍然是有效的。”

乔治·康托尔是第一个利用这种力量的人，他是集合论数学领域的创始人。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年，贝克、吉尔和索洛维证明了复杂性理论中许多未解决的问题无法仅通过对角化来解决。其中最重要的是著名的P/NP问题，该问题简单来说是关于能否在多项式时间内验证解的正确性以及是否能在多项式时间内求解的问题

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

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

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

如果你想证明某些事情是不可能的，不要低估否定的力量

原文链接：

需要重写的内容是：https://www.quantamagazine.org/alan-turing-and-the-power-of-negative-thinking-20230905/

以上是重温图灵原理，感受反证法的力量的详细内容。更多信息请关注PHP中文网其他相关文章！