算法已经变得无处不在，似乎对于每一个可以用精确数学术语表达的课题，都有一种对应的算法。但事实并非如此，其实一些看似简单的课题永远没法用算法处理。
算计机科学家中的先驱艾伦・图灵，曾在近一个世纪前的一篇论文中说明了这种「弗成算计」课题的消失，他提出了启动现代算计机科学的算计数学模型。
图灵用一种违反直觉的策略说明了这一突破性的结果：他界说了一个课题，一个拒绝一切试图处理它的方法的课题。「比如我问你在做什么，不管你回答什么我都会说，‘我要做的事情和你说的不一样’。」麻省理工学院研究实际算计机科学的研究生 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/