算法已经变得无处不在。它们优化我们的通勤、处理支付并协调互联网流量。
只要可以用精确的数学术语表达的问题（问题空间），都有一种算法可以解决它？（解决方案空间）
但事实并非如此：一些看似简单的问题永远无法通过算法解决。
计算机科学家先驱艾伦·图灵在近一个世纪前证明了此类“不可计算”问题的存在，在同一篇论文中，他制定了启动现代计算机科学的计算数学模型。
图灵使用一种反直觉的策略证明了这一突破性的结果：他定义了一个问题，并拒绝所有解决该问题的尝试。
图灵的策略基于一种称为对角化的数学技术，该技术具有悠久的历史。
下面是他的证明背后逻辑的简化说明。
String理论
对角化源于解决一个普通问题的巧妙技巧，这个问题涉及比特串，每个比特串都可以是 0 或 1。给定一个长度相同的字符串列表，你能生成一个不在列表中的新字符串吗？
最直接的策略是依次考虑每个可能的字符串。假设有五个字符串，每个都是五比特长。首先在列表中扫描 00000。如果没有，就停止；如果有，就转到 00001，然后重复这个过程。这样做很简单，但对于长字符串的长列表来说，速度很慢。
对角化是另一种方法，它可以将丢失的字符串逐位建立起来。从列表中第一个字符串的第一位开始反转，这就是新字符串的第一位。然后反转第二个字符串的第二位，将其作为新字符串的第二位，如此重复，直到列表结束。您翻转的位可以确保新字符串与原始列表中的每个字符串至少有一处不同。(它们还在字符串列表中形成一条对角线，这也是这项技术名称的由来）。
对角化只需检查列表中每个字符串的一个比特，因此通常比其他方法快得多。但它的真正威力在于它能很好地处理无穷大。
"麻省理工学院的理论计算机科学家莱恩-威廉姆斯（Ryan Williams）说："字符串现在可以是无限的，列表也可以是无限的，但它仍然有效。
第一个利用这种能力的人是格奥尔格-康托尔，他是集合论这一数学子领域的创始人。1873 年，康托尔利用对角化证明了某些无穷大比其他无穷大更大。六十年后，图灵将康托尔版本的对角线化应用到计算理论中，使其带有明显的反传统色彩。
限制游戏
图灵希望证明存在任何算法都无法解决的数学问题--即输入和输出定义明确，但从输入到输出却没有万无一失的程序的问题。他将注意力完全集中在决策问题上，使这一模糊的任务变得更容易处理，在决策问题中，输入可以是任何一串 0 和 1，输出则是 0 或 1。
判断一个数字是否是质数（只能被 1 和它本身整除）就是决策问题的一个例子--给定一个代表数字的输入字符串，如果数字是质数，正确的输出是 1，如果不是，正确的输出是 0。另一个例子是检查计算机程序的语法错误（相当于语法错误）。在这里，输入字符串代表不同程序的代码--所有程序都可以这样表示，因为它们就是这样在计算机上存储和执行的--而目标是如果代码包含语法错误，则输出 1；如果不包含，则输出 0。
一个算法只有在对每一个可能的输入都能产生正确的输出时，它才算解决了一个问题--如果它失败了哪怕一次，它就不是一个解决该问题的通用算法。通常情况下，你会先指定要解决的问题，然后尝试找到一种算法来解决它。图灵在寻找无法解决的问题时，颠覆了这一逻辑--他想象了一个包含所有可能算法的无限列表，并使用对角法构建了一个顽固的问题，该问题将挫败列表中的每一种算法。
试想一下，在一个由 20 道题组成的游戏中，答题者不是一开始就想到某个特定的对象，而是为拒绝每道题编造一个借口。到游戏结束时，他们已经描述了一个完全由它所缺乏的品质定义的物体。
图灵的对角线化证明是这个游戏的一个版本，在这个游戏中，问题贯穿了可能算法的无限列表，反复问："这个算法能解决我们想证明的不可计算的问题吗？"
"威廉姆斯说："这有点像'无穷大问题'。
为了赢得比赛，图灵需要精心设计一个问题，让每个算法的答案都是 "不"。这意味着要找出一个能让第一个算法输出错误答案的特殊输入，另一个能让第二个算法失败的输入，以此类推。他找到这些特殊输入的方法类似于库尔特-哥德尔（Kurt Gödel）最近用来证明 "此语句无法证明 "等自反论断给数学基础带来麻烦的方法。
关键的见解是，每种算法（或程序）都可以表示为一串 0 和 1。这意味着，就像错误检查程序的例子一样，一种算法可以把另一种算法的代码作为输入。原则上，一个算法甚至可以把自己的代码作为输入。
有了这样的洞察力，我们就可以定义一个不可计算的问题，就像图灵证明中的问题一样："给定一个代表算法代码的输入字符串，如果该算法以自己的代码为输入时输出 0，则输出 1；否则，输出 0。每个试图解决这个问题的算法都会在至少一个输入上产生错误的输出--即对应于自身代码的输入。这意味着，任何算法都无法解决这个反常的问题
否定式无法实现的功能
计算机科学家还没有完成对角化。1965 年，尤里斯-哈特曼尼斯（Juris Hartmanis）和理查德-斯特恩斯（Richard Stearns）对图灵的论点进行了改编，证明并非所有可计算问题都是相同的--有些问题本质上比其他问题更难。
这一结果开创了计算复杂性理论领域，研究计算问题的难度。
但复杂性理论也揭示了图灵相反方法的局限性。1975 年，西奥多-贝克（Theodore Baker）、约翰-吉尔（John Gill）和罗伯特-索洛维（Robert Solovay）证明，复杂性理论中的许多悬而未决的问题永远无法仅靠对角线法来解决。其中最主要的是著名的 P 对 NP 问题，即是否所有具有易查解法的问题都可以用正确巧妙的算法轻松解决。
对角化的盲点是使其如此强大的高度抽象化的直接后果。图灵的证明并不涉及任何在实践中可能出现的无法计算的问题--相反，它临时编造了这样一个问题。其他对角线化证明同样远离现实世界，因此无法解决现实世界中细节重要的问题。
对角化的失败很早就表明，解决 P 对 NP 问题将是一个漫长的过程。
尽管存在局限性，对角化仍然是复杂性理论家的重要工具之一。2011 年，威廉姆斯利用它和其他一系列技术证明，某种受限的计算模型无法解决一些异常困难的问题--这是研究人员 25 年来一直无法解决的问题。虽然这与解决 P 对 NP 的问题相去甚远，但它仍然代表着重大进展。
如果你想证明某些事情是不可能的，不要低估说 "不 "的力量。