从未建造过的最重要的机器

计算是我们大多数人凭直觉就能理解的一个熟悉的概念。取函数f(x) = x + 3。当x为三时，f(3) = 3+3，结果是6，这很简单。很明显这个函数是可计算的。但有些函数并不是那么简单，而且要确定它们是否可以计算也不是那么容易，这意味着它们可能永远不会给我们最终答案。

1928 年，德国数学家大卫·希尔伯特和威廉·阿克曼提出了一个名为Entscheidungsproblem（“决策问题”）的问题。随着时间的推移，他们的问题将导致可计算性的正式定义，使数学家能够回答大量新问题并为理论计算机科学奠定基础。

这个定义来自一位名叫艾伦·图灵的23岁研究生，他在1936年写了一篇开创性的论文，不仅正式化了计算的概念，而且证明了数学中的一个基本问题，并为电子计算机的发明奠定了智力基础。图灵的伟大见解是以抽象机器的形式为计算问题提供了具体的答案，后来他的博士顾问阿隆佐·丘奇将其命名为图灵机器。它是抽象的，因为它不是（也不可能）以有形设备的形式存在。相反，它是一个概念计算模型：如果机器可以计算一个函数，那么这个函数是可计算的。

这是它的工作原理。图灵机可以按照规则表的规定读取和更改无限长磁带上的符号。磁带由“单元”组成，每个单元只能存储一个符号，机器用磁带头读取和重写单元的内容。表中的每条规则都根据机器的当前状态和它正在读取的符号来确定机器应该做什么。机器可以进入最终状态（“接受状态”或“拒绝状态”），然后停止，接受或拒绝输入。或者它陷入无限循环并永远继续读取磁带。

理解图灵机的最好方法是考虑一个简单的例子。让我们想象一个旨在告诉我们给定输入是否为数字零的程序。我们将使用带有空白符号(#)的输入数字0001，因此“#0001#”是我们磁带的相关部分。

机器从初始状态开始，我们称之为 q0。它读取磁带上最左边的单元并找到一个空白区域。规则规定，“当处于状态 q0 时，如果符号是#，则保持原样不变，向右移动一个单元格，并将机器的状态更改为q1。” 在这一步之后，机器处于状态q1，它的头部正在读取第二个符号0。

现在我们寻找适用于这些条件的规则。我们发现一个说，“保持状态q1并将头部向右移动一个单元。” 这使我们处于相同的位置（在状态 q1 中，读数为“0”），因此我们继续向右移动，直到磁头最终读取到一个不同的数字，即1。

当我们再次查阅表格时，我们发现了一条新规则：“如果我们遇到1，则转换到q2，这是一种‘拒绝’状态。”机器停止，对原始问题“‘0001’为零吗？”回答“否”

如果输入为“#0000#”，则机器将在所有这些零之后遇到一个#。当我们查阅表格时，我们发现一条规则说，这意味着机器进入状态q3，即“接受”状态。现在机器对“0000是零吗？”这个问题回答“是”

通过他的抽象机器，图灵建立了一个计算模型来回答Entscheidungs问题，该问题正式提出以下问题：给定一组数学公理，是否存在一个机械过程——一组指令，今天我们称之为算法——总是可以确定给定的陈述是否为真？

假设我们想找到一种算法来告诉我们某个棋局是否可行。在这里，公理是管理合法移动的国际象棋规则。我们能否按照有限的逐步程序序列到达该位置？尽管某些局面可能需要比我们一生更长的时间来分析——一种算法可能会生成所有可能的局面并将它们中的每一个与输入进行比较——但此类算法存在于国际象棋游戏中。因此，我们说国际象棋是“可判定的”。

然而，在1936年，Church和Turing使用不同的方法独立证明，没有通用的方法来解决Entscheidungs问题的每一个例子。例如，一些游戏，如约翰·康威的《生命的游戏》，是不可决定的：没有算法可以确定某个模式是否会从初始模式中出现。

图灵表明，如果存在可以执行所需任务的算法，则函数是可计算的。同时，他表明算法是一个可以用图灵机定义的过程。因此，可计算函数是具有图灵机来计算它的函数。这似乎是一种定义可计算性的迂回方式，但这是我们所拥有的最好的方式。麻省理工学院理论计算机科学家Michael Sipser说：“这并不是说你可以选择用其他方式来定义它。我认为人们普遍认为，Church-Turing论文说算法的非正式概念对应于任何‘合理的’计算模型可以做的事情。” 其他数学家提出了不同的计算模型，这些模型表面上看起来很不一样，但实际上是等价的：它们可以进行图灵机可以进行的任何计算，反之亦然。

就在库尔特·哥德尔证明数学是不完备的几年之后 ，丘奇和图灵通过这项工作表明数学中的一些问题是不可判定的——无论算法多么复杂，都无法告诉我们答案是肯定还是否定。这两件事对希尔伯特来说都是毁灭性的打击，他曾希望数学能给出简洁、理想化的答案。但这也许也一样：如果存在解决问题的一般解决方案，这将意味着数学中的所有问题都可以简化为简单的机械计算。

除了回答这些基本问题之外，图灵机还通过一种称为通用图灵机的变体直接导致了现代计算机的发展。这是一种特殊的图灵机，可以在任何输入上模拟任何其他图灵机。它可以读取其他图灵机的描述（它们的规则和输入磁带）并在自己的输入磁带上模拟它们的行为，产生与模拟机器产生的相同的输出，就像今天的计算机可以读取任何程序并执行它一样。1945 年，约翰·冯·诺依曼提出了一种计算机架构——称为冯·诺依曼架构——使通用图灵机概念在现实生活中的机器中成为可能。

当普林斯顿大学的理论计算机科学家Sanjeev Arora教授这个概念时，他强调了更广泛的哲学图景。“‘普遍’有两种概念，”他说。“通用的一个概念是它可以运行任何其他图灵机。但另一个更广泛的‘通用’概念是它可以运行你在宇宙中想出的任何计算。” 在经典物理学的世界中，任何物理过程都可以使用算法进行建模或模拟，而算法又可以由图灵机进行模拟。

另一个值得注意且越来越有用的变体是概率图灵机。与对每个输入都有明确定义的反应的常规图灵机不同，概率图灵机可以根据概率做出多种反应。这意味着它可以在不同的时间对相同的输入产生不同的结果。令人惊讶的是，对于某些问题，这种概率策略比纯确定性方法更有效。概率图灵机的思想已被证明在密码学、优化和机器学习等领域非常有用。

这些抽象机器也许是最好的证据，证明提出基本问题是科学家能做的最有用的事情之一。