否定的力量：图灵的对角化证明
概要：
图灵通过对角化方法证明了某些问题是算法无法解决的“不可计算”问题，这一突破性成果展示了算法的局限性。对角化通过构建一个特殊的自我否定问题，反复回答“这个算法可以解决我们要证明的不可计算问题吗”，迫使每一个算法在某个输入上失败，从而证明这个问题不可计算。虽然对角化强大，但它过于抽象，无法处理需要考虑实际情况的问题，如P与NP问题。然而对角化仍是复杂性理论的关键工具。如果要证明某事不可能，不可小看仅仅说“不”的力量。
基于对角化技术的数学证明可以十分反传统，但它们帮助揭示算法的局限。
算法已经无处不在。它们优化我们的通勤，处理支付并协调互联网流量。似乎对于每一个可以用精确的数学术语表达的问题，理论上都存在可以解决它的算法。
但事实并非如此，一些看似简单的问题永远无法用算法解决。计算机科学先驱艾伦·图灵近一个世纪前就证明了这种“不可计算”问题的存在性，正是在他形成现代计算机科学基础的计算数学模型的同一篇论文中。
图灵使用一种反直觉的策略证明了这一突破性结果:他定义了一个简单拒绝每一次解决尝试的问题。
“我问你在做什么，然后我说，‘不，我要做不同的事情，’”麻省理工学院的理论计算机科学研究生拉胡尔·伊兰戈说。
图灵的策略基于一种称为对角化的数学技术，这种技术有着杰出的历史。下面是他证明背后的逻辑的简化说明。
字符串理论
对角化源自解决一个涉及位串的乏味问题的巧妙技巧，每串中的每个位可以是0或1。给定一系列等长的这样的串，你能生成一个不在列表上的新串吗?
最直接的策略是依次考虑每一个可能的串。假设你有5个串，每个5位长。首先查看列表查找00000。如果不在，你可以停止;如果在，则继续检查00001，重复这个过程。对长列表长串来说这很简单，但速度很慢。
对角化是一种替代方法，逐位构建缺失的串。从列表上的第一个串的第一位开始，将其取反——这将是新串的第一位。然后取反第二个串的第二位，并将其用作新串的第二位，以此类推直到列表结束。你翻转的位确保新串与原始列表上的每个串至少有一处不同。(它们也在字符串列表中形成对角线，这就是该技术的名称来源。)
对角化只需要检查列表上每个串的一位，所以它通常比其他方法快得多。但它的真正力量在于它与无穷的契合程度。
“现在字符串可以是无限的；列表可以是无限的，它仍然有效，”麻省理工学院的理论计算机科学家瑞安·威廉姆斯说。
第一个利用这种力量的人是集合论数学子领域的创始人格奥尔格·康托尔。1873年，康托尔使用对角化证明了某些无穷大大于其他无穷大。60年后，图灵改编了康托尔的对角化版本应用于计算理论，赋予其明显的反传统特征。
局限的游戏
图灵想证明存在算法无法解决的数学问题，也就是说，这些问题有明确定义的输入和输出，但没有万无一失的从输入到输出的过程。他通过将注意力仅集中在决策问题上使这个模糊的任务变得更可管理，决策问题中的输入可以是任何0和1的串，输出是0或1。
判断一个数是否为素数(只能被1和自身整除的数)是一个决策问题的例子，给定表示一个数的输入串，如果该数是素数，正确的输出是1;如果不是，输出是0。另一个例子是检查计算机程序的语法错误(相当于语法错误)。在这种情况下，输入串表示不同程序的代码，所有程序都可以以这种方式表示，因为这就是它们在计算机上存储和执行的方式，目标是如果代码包含语法错误输出1，如果没有输出0。
只有当一个算法对每一个可能的输入都产生正确的输出时，该算法才解决了一个问题，哪怕失败一次，它就不是那个问题的通用算法。通常，你会首先指定要解决的问题，然后尝试找到解决它的算法。图灵为了寻找不可解决的问题，逆转了这个逻辑，他想象了一个包含所有可能算法的无限列表，并使用对角化构建了一个顽固的问题，可以挫败列表上的每一个算法。
想象一个造作的20问游戏，其中回答者不是从一开始就有一个特定的对象，而是想出借口对每个问题说不。到游戏结束时，他们已经描述了一个完全由所缺乏的品质定义的对象。
图灵的对角化证明是这个游戏的一个版本，其中问题遍历可能算法的无限列表，反复问:"这个算法可以解决我们想证明不可计算的问题吗?"
“这有点像'无穷问题'，”威廉姆斯说。
为了赢得这场游戏，图灵需要设计一个对每个算法答案都是no的问题。这意味着识别一个特定的输入，使第一个算法输出错误的答案，另一个输入使第二个算法失败，等等。他使用类似于古德尔最近用来证明像“这句话不可证明”这样的自引证言难以成立的技巧，找到了这些特殊的输入。
关键洞见是每个算法(或程序)都可以表示为0和1的串。这意味着，就像错误检查程序的例子一样，一个算法可以将另一个算法的代码作为输入。原则上，一个算法甚至可以将自己的代码作为输入。
有了这一洞察，我们可以定义一个像图灵证明中那样不可计算的问题:“给定表示一个算法代码的输入串，如果该算法在自己的代码作为输入时输出0，则输出1;否则输出0。” 每个试图解决这个问题的算法在至少一个输入上都会产生错误输出，即对应它自己的代码的输入。这意味着这个反常问题无法被任何算法解决。
否定无法做什么
计算机科学家还没有通过对角化。1965年，尤利斯·哈特曼尼斯和理查德·斯特恩斯改编了图灵的论证，证明了并非所有可计算问题都是平等的，有些本质上比其他更难。这个结果启动了计算复杂性理论领域的研究，该领域研究计算问题的难度。
但复杂性理论也揭示了图灵反面的方法的局限。1975年，西奥多·贝克、约翰·吉尔和罗伯特·所罗门证明，许多开放的复杂性理论问题永远无法仅通过对角化解决。其中最著名的是P与NP问题，该问题询问是否所有易检查解决方案的问题也都有恰当的巧妙算法易于解决。
对角化的盲区是其强大抽象级别的直接结果。图灵的证明没有涉及任何可能在实践中出现的不可计算问题，而是即时编造这样一个问题。其他对角化证明同样与现实世界保持距离，因此它们无法解决现实细节很重要的问题。
“他们从远处处理计算，”威廉姆斯说。“我想象一个通过手套箱处理病细节人的人。”
对角化的失败是解决P与NP问题将是一段漫长旅程的早期迹象。但尽管有局限，对角化仍然是复杂性理论家们武器库中关键工具之一。2011年，威廉姆斯结合对角化和大量其他技术证明了某种受限的计算模型无法解决一些非常困难的问题，这个结果令研究者操心了25年之久。与解决P与NP问题相去甚远，但它仍代表了重大进步。
如果你想证明某事不可能，不要低估仅仅说不的力量。
本文译自 Quanta Magazine，由 BALI 编辑发布。