可计算性理论和复杂性简介

已发表: 2022-03-11

你有没有想过：你正在阅读这篇文章的设备到底是什么？电脑是什么？

计算科学可以追溯到远在这些现代计算设备被想象出来之前的一段时间。在一个更常见的问题围绕编程语言、框架和库的行业中，我们经常认为使计算机运行的基本概念是理所当然的。

但是这些似乎拥有无穷潜力的计算机——它们有什么限制吗？有没有电脑不能解决的问题？

在本文中，我们将通过远离编程语言和计算机体系结构的细节来解决这些问题。通过了解计算机和算法的力量和局限性，我们可以改进我们的思维方式，更好地推理不同的策略。

计算的抽象视图产生的结果经受住了时间的考验，对今天的我们来说就像它们在 1970 年代最初开发时一样有价值。

可计算性

电脑是什么？什么是问题？

在学校里，我们经常被教导一个问题和功能的心理模型，如下所示：

函数是您应用到输入 x 以找到输出 f(x) 的过程。

原来数学定义是不同的：

函数是一组有序对，其中每对的第一个元素来自集合 X（称为域），每对的第二个元素来自集合 Y（称为共域或范围），并且域与范围中的一个元素配对。

那真是满口。但是，这究竟是什么意思？

这个定义告诉我们，计算机是计算功能的机器。

为什么？

因为计算机将任意输入转换为某些输出。换句话说，他们解决问题。函数的两种定义，一种是我们非常熟悉的，一种是正式的，在许多实际目的上是一致的。

然而，数学定义允许我们得出有趣的结论，例如存在不可计算的函数（即不可解决的问题）：

因为，并不是每个函数都可以描述为一种算法。

游戏规则

为了帮助我们论证，让我们将计算机想象成机器，接受一些输入，执行一系列操作，并在一段时间后给出一些输出。

我们将输入机器的字母表；也就是说，来自某个有限集合的一组字符串。例如，机器的字母可能是二进制（0 和 1），也可能是 ASCII 字符集。任何有限的字符序列都是字符串，例如“0110”。

此外，我们将机器的输出表示为二进制接受-拒绝决策，一旦机器（希望）完成其计算就交付。这种抽象很适合早先对函数的数学定义。

给定这些参数，重要的是要表征另一种类型：字符串集合。也许我们关心某些机器接受的字符串集合，或者我们正在构建一台机器，它只接受特定集合中的字符串而不接受其他字符串，或者我们可能在问是否有可能设计一台机器接受某些字符串中的所有内容特定的集合，没有其他的。

在所有这些情况下，一组字符串称为一种语言——例如，表示偶数的所有二进制字符串的集合或具有偶数个字符的字符串的集合。事实证明，语言，如数字，可以使用连接、联合、交集等运算符进行操作。

一个重要的运算符是也与正则表达式一起使用的 Kleene 星号运算符。这可以被认为是语言所有可能的力量的结合。例如，如果我们的语言A是字符串集合 { '01', '1' }，那么A*的一个成员就是字符串 '0101111'。

可数性

在我们证明并非所有函数都是可计算的说法之前，最后一个难题是可数性的概念。直观地说，我们的证明将表明存在更多的语言；也就是说，问题多于解决这些问题的可能程序。这是有效的，因为字符串是否属于一种语言（是/否）的问题本身就是一个问题。

更准确地说，我们的证明声称可能的程序集是可数无限的，而字母表上的语言集是不可数无限的。

在这一点上，你可能会想，“无限本身就是一个很奇怪的想法；现在我要对付他们两个！”

好吧，这还不错。可数无限集是可以枚举的。可以说这是第一个元素，这是第二个元素，依此类推，最终为集合的每个元素分配一个数字。以偶数集为例。我们可以说 2 是第一个，4 是第二个，6 是第三个，依此类推。这样的集合是可数无限或可数的。

但是，对于某些集合，例如实数，您有多聪明并不重要。根本没有枚举。这些集合是不可数无限或不可数的。

可数很多程序

首先，我们要证明计算机程序集是可数的。出于我们的目的，我们通过观察有限字母表上所有字符串的集合是可数的来做到这一点。这是有效的，因为计算机程序本身就是有限字符串。

证明很简单，我们在这里不详细介绍。关键的一点是，计算机程序的数量与自然数一样多。

重申：

任何字母表上的所有字符串的集合（例如，所有计算机程序的集合）都是可数的。

无数种语言

鉴于这个结论，这些字符串的子集呢？换一种方式问，所有语言的集合呢？事实证明，这个集合是不可数的。

任何字母表上的所有语言的集合都是不可数的。

再一次，我们不在这里讨论证明。

结果

尽管它们可能不会立即显现出来，但语言的不可数性和所有计算机程序的集合的可数性的后果是深远的。

为什么？

假设A是 ASCII 字符集； ASCII 字符只是编写计算机程序所需的字符。我们可以看到，表示 JavaScript 程序的字符串集是A*的子集（这里，* 是 Kleene 星号运算符）。 JavaScript 的选择是任意的。由于这组程序是可数集的子集，因此我们认为 JavaScript 程序集是可数的。

此外，让我们考虑对于任何语言L ，我们可以定义一些函数f ，如果某个字符串x在L中，则其值为 1，否则为 0。所有这些功能都是不同的。因为与所有语言的集合有 1:1 的对应关系，并且因为所有语言的集合都是不可数的，所以我们有所有这些函数的集合都是不可数的。

这是深刻的一点：

由于所有有效程序的集合是可数的，但函数的集合不是，那么肯定有一些函数我们根本无法编写程序。

我们还不知道这些功能或问题是什么样的，但我们知道它们存在。这是一个令人羞愧的认识，因为存在一些没有解决方案的问题。我们认为计算机非常强大和有能力，但有些事情甚至超出了他们的能力范围。

现在问题变成了，“这些问题是什么样的？” 在我们继续描述这些问题之前，我们必须首先以广义的方式对计算进行建模。

图灵机

最早的计算机数学模型之一是由艾伦·图灵开发的。这个模型，称为图灵机，是一个非常简单的设备，完全符合我们的可计算性概念。

机器的输入是输入已写入的磁带。使用读/写头，机器通过一系列步骤将输入变为输出。在每个步骤中，都会决定是否写入磁带以及写入磁带的内容以及是否将其向右或向左移动。这个决定完全基于两件事：

头部下方的当前符号，以及
机器的内部状态，也随着符号的写入而更新

而已。

普遍性

1926 年，艾伦·图灵（Alan Turing）不仅开发了图灵机，而且在撰写他的著名论文《论可计算数》时对计算的本质有了许多其他重要见解。他意识到计算机程序本身可以被视为计算机的输入。有了这个观点，他有了一个美妙的想法，即图灵机可以模拟或执行该输入。

虽然我们今天认为这些想法是理所当然的，但在图灵时代，这种通用机器的想法是让图灵开发无法解决的问题的重大突破。

教会图灵论

在继续之前，让我们检查一个重点：我们知道图灵机是一种计算模型，但它是否足够通用？为了回答这个问题，我们求助于 Church-Turing Thesis，它证实了以下陈述：

一切可计算的东西都可以用图灵机计算。

在图灵开发图灵机作为计算模型的同时，Alonzo Church 还开发了一种称为 lambda 演算的计算模型。这些模型非常强大，因为它们既描述了计算，又以与今天的任何计算机或任何计算机相同的方式来描述计算。这意味着我们可以使用图灵机来描述我们寻求的无法解决的问题，因为我们知道我们的发现将适用于过去、现在和以后所有可能的计算机。

可识别性和可判定性

在具体描述一个无法解决的问题之前，我们必须多介绍一点背景知识，即语言识别器和语言决定器的概念。

如果有图灵机可以识别语言，则该语言是可识别的。
和
如果有一个图灵机来决定一种语言，那么它就是可决定的。

要成为一种语言的识别器，图灵机必须接受该语言中的每个字符串，并且它不能接受任何不是该语言的字符串。它可能会拒绝或循环此类字符串。要成为决策者，图灵机必须始终通过接受或拒绝来停止其输入。

在这里，停止输入的想法至关重要。事实上，我们看到决策者比识别者更强大。此外，一个问题是可解决的，或者换句话说，一个函数只有在存在决定函数所描述的语言的图灵机时才是可判定的。

不确定性

如果您曾经编写过计算机程序，那么您肯定知道当程序执行时坐在那儿看着计算机旋转的感觉。您不知道程序是否只是花费了很长时间，或者代码中是否存在某些错误导致无限循环。您甚至可能想知道为什么编译器不检查代码以查看它在运行时是否会停止或永远循环。

编译器没有这样的检查，因为它根本无法完成。并不是编译器工程师不够聪明或缺乏资源；根本不可能检查任意计算机程序以确定它是否停止。

我们可以使用图灵机来证明这一点。图灵机可以被描述为字符串，因此它们的数量是可数的。假设 M ₁ 、 M ₂等构成所有图灵机的集合。让我们定义以下函数：

f(i, j) = 1 如果 M _i接受 <M _j >，否则为 0

这里，<M> 是“M 的字符串编码”的语法，这个函数表示如果 M _i通过接受 M _j作为输入而停止输出 1，否则输出 0 的问题。请注意，M _i必须停止（即，成为决策者）。这是必需的，因为我们希望描述一个不可判定的函数（即，不可解决的问题）。

现在，让我们也定义一种语言L ，它由不接受自身描述的图灵机的字符串编码组成：

L = { <M> | M 不接受 <M> }

例如，某台机器 M ₁可能在输入 <M ₁ > 上输出 0，而另一台机器 M ₂可能在输入 <M ₂ > 上输出 1。为了证明这种语言是不可判定的，我们询问决定语言 L 的机器 M _L当它自己的描述 <M _L > 作为输入时会做什么。有两种可能：

M _L接受 <M _L >
要么
M _L拒绝 <M _L >

如果 M _L接受它自己的编码，那么这意味着 <M _L > 不在语言 L 中；然而，如果是这样的话，那么 M _L一开始就不应该接受它的编码。另一方面，如果 M _L不接受它自己的编码，那么 <M _L > 在语言 L 中，所以 M _L应该接受它的字符串编码。

在这两种情况下，我们都有一个悖论，或者用数学术语来说，一个矛盾，证明语言 L 是不可判定的；因此，我们已经描述了我们的第一个无法解决的问题。

停机问题

虽然我们刚刚描述的问题可能看起来无关紧要，但它可以简化为具有实际重要性的其他无法解决的问题，最值得注意的是停机问题：

图灵机在空字符串上停止的编码语言。

停止问题适用于为什么编译器无法从早期检测到无限循环的问题。如果我们不能确定一个程序是否在空字符串上终止，那么我们怎么可能确定它的执行是否会导致一个无限循环呢？

在这一点上，我们似乎只是为了得出一些简单的结论而挥手而已；然而，我们实际上意识到，没有图灵机可以判断计算机程序是否会停止或永远保持在循环中。这是实际应用中的一个重要问题，在图灵机或任何其他类型的计算机上都无法解决。 iPhone 无法解决这个问题。多核台式机无法解决这个问题。云无法解决这个问题。即使有人发明了一台量子计算机，它仍然无法解决停机问题。

概括

在我们对可计算性理论的研究中，我们已经看到有许多函数在任何普通意义上是无法通过计数参数计算的。我们精确地定义了我们所说的计算的含义，一直追溯到图灵从他自己的笔和纸经验中获得的灵感，从而形式化了图灵机。我们已经看到这个模型如何计算任何今天的计算机或未来设想的计算机可以计算的任何东西，并且我们意识到了一类根本无法计算的问题。

尽管如此，可计算性也有不利之处。仅仅因为我们可以解决问题并不意味着我们可以快速解决它。毕竟，如果计算机的计算不能在未来数千万年的太阳对我们产生新星之前完成，那计算机有什么用呢？

抛开可计算函数和语言，我们现在讨论计算复杂性、调查高效计算和著名的 P 与 NP 问题。

复杂

慢与快

计算机科学家认识到各种各样的问题，我们关心的两类问题包括计算机可以快速或有效地解决的问题，称为P和解决方案可以快速验证但不能快速获得的问题，称为NP 。

例如，假设您负责开发在线约会服务的算法，有人提出问题：“每个人都可以约会吗？” 答案归结为配对兼容的个人，以便每个人都配对。事实证明有解决这个问题的有效算法。这个问题在集合P中。

好吧，如果我们想确定用户中最大的集团怎么办？我们所说的集团是指彼此兼容的最大的个人网络。当用户数较少时，这个问题可以很快得到解决。我们可以很容易地识别出一个有 3 个用户的集团。然而，当我们开始寻找更大的集团时，问题变得越来越难以解决。这个问题在集合NP中。

正式定义

P是在多项式时间内可解决的问题的集合。也就是说，计算步骤的数量由关于问题大小的多项式函数限制。我们知道“每个人都可以约会吗？” 问题，也称为二分匹配问题，在P中。

NP是在多项式时间内可验证的问题集。当然，这包括 P 中的所有问题；但是，我们不知道这种收容措施是否严格。我们知道可以有效验证但无法有效解决的问题，但我们不知道问题是否真的难以解决。集团问题就是这样一个问题。我们知道我们可以有效地验证解决方案，但我们不确定是否可以有效地解决问题。

最后， NP-complete是NP中最难的问题集。它们被称为最难的，因为NP中的任何问题都可以有效地转化为NPC 。结果，如果有人要找出NPC问题的有效解决方案，那么整个NP类都将被P吸收。派系问题也在NPC中。

因此，我们遇到了P与NP的问题。许多计算机科学家和数学家坚信P和NP不相等。如果是这样，其影响将是深远的。今天的大部分数字基础设施都依赖于这样一个事实，即NP中存在P中没有的问题。如果不是这种情况，例如，加密方法将在一夜之间崩溃，从而使拥有有效解决NPC问题的人能够颠覆甚至最严格的安全协议。

可追踪性的细微之处

对于计算机科学新手来说，匹配问题和集团问题之间的区别可能看起来没什么大不了的。事实上， P中的问题和NP中的问题之间的差异可能非常微妙。对于在现实世界中设计算法的任何人来说，能够分辨出差异都很重要。

考虑最短路径问题。给定两个位置，目标是确定它们之间的最短路径。 iPhone 可以在几毫秒内完成计算。这是一个计算上易于处理的问题。

另一方面，考虑旅行推销员问题，其目标是访问以起点为终点的可能目的地的子集，同时行驶尽可能短的距离。这个问题类似于最短路径问题，但是是 NP 完全的；它还解释了为什么供应链物流是一个十亿美元的产业。

我们实际上可以更微妙。我们可以不求最短路径（P），而是求最长无环路径。原来最长路径问题也是NP完全的。

这种微妙区别还有更多示例，包括识别二分图与一般图中的顶点覆盖或满足每个子句两个与三个文字的布尔公式。关键是问题是在 P 还是 NP 并不是很明显，这就是为什么运行时间分析是一项关键技能。如果必须设计的算法是针对 P 中的一个问题，那么我们就知道有一个有效的解决方案。另一方面，如果问题出在 NP 中，那么我们有充分的理由反对寻求解决方案，因为算法通常需要很长时间才能解决问题。

概括

在对复杂性的检查中，我们定义了问题 P 和 NP 的类别。 P 非正式地表示可以由计算机有效解决的问题，而 NP 表示可以有效验证的问题。

没有人能够证明 P 不等于 NP。这两类问题是否等价被称为 P 与 NP 问题，它是当今理论计算机科学中最重要的开放问题，如果不是在所有数学中的话。事实上，在 2000 年，克莱数学研究所将 P 与 NP 问题命名为数学中七个最重要的开放性问题之一，并悬赏百万美元悬赏确定该问题的解决方案的证明。

结论

在本文中，我们深入研究了可计算性和复杂性领域，回答了诸如“什么是计算机？”之类的大问题。虽然细节可能是压倒性的，但有一些深刻的要点值得记住：

有些事情根本无法计算，例如停机问题。
有些事情无法有效计算，例如 NPC 中的问题。

比细节更重要的是思考计算和计算问题的方法。在我们的职业生涯甚至日常生活中，我们可能会遇到从未见过的问题，我们可以使用久经考验的真实工具和技术来确定最佳行动方案。

进一步阅读 Toptal 工程博客：

如何从头开始编写解释器