在自然科学中，大自然给了我们一个世界，我们只是发现它的规律。在计算机中，我们可以将规律融入其中来创造一个世界。 －Alan Kay 我们的领域仍处于萌芽阶段。2000 年来我们都没有发现它是件很棒的事。我们仍然处于一个非常非常重要的结果不断出现在我们眼前的阶段。 ——Michael Rabin，关于计算机科学 算法（algorithm）是计算机科学中的关键概念。算法是执行某些任务的精确方法，例如我们在孩提时代都学过的两数相加的基本算法。本章将概述在计算机科学中发展的现代算法理论。我们刻画算法的基本模型是图灵机（Turing Machine）。这是一台理想化的计算机，非常像一台现代个人电脑，但具有更简单的基本指令集和理想化的无限内存。图灵机表面上构造简单，这常常令人误解；实际上它们是非常强大的设备。我们将看到它们可用于执行任何算法，甚至是那些在看似强大得多的计算机上运行的算法。
我们在算法研究中试图解决的基本问题是：执行给定的计算任务需要哪些资源？这个问题自然地分为两部分。首先，我们想了解哪些计算任务是可能的，最好是通过提供解决特定问题的显式算法。例如，我们有许多优秀的算法实例，可以快速将数字列表按升序排序。其次是论证关于可以完成哪些计算任务的限制。例如，我们可以给出任何将数字列表按升序排序的算法所必须执行的操作数量的下界。理想情况下，这两项任务——找寻解决计算问题的算法，以及证明我们解决该计算问题的能力的局限性——将完美地吻合。在实际中，解决某个计算问题的最佳技术与关于解决方案最严格的限制之间通常存在着显著差距。本章的目的是概述为帮助分析计算问题，以及构造和分析解决这些问题的算法而发展的工具。
为什么对量子计算和量子信息感兴趣的人需要花时间去研究经典计算机科学？对此有三个很好的理由。首先，经典计算机科学提供了大量的概念和技术，可以在量子计算和量子信息中重复
使用并发挥巨大的作用。量子计算和量子信息的许多成果都是通过将计算机科学中的现有思想与量子力学的新思想相结合而产生的。例如，量子计算机的一些快速算法基于傅里叶变换的，这是许多经典算法所使用的强大工具。自人们认识到量子计算机可以比经典计算机快得多地执行一类傅里叶变换，这使得许多重要的量子算法得以发展出来。
其次，计算机科学家花费了很多精力来理解在经典计算机上执行给定的计算任务需要哪些资源。这些结果可以用作与量子计算和量子信息进行比较的基础。例如，人们集中了大量的注意力在寻找给定数字的素因子问题上。人们相信这个问题在经典计算机上没有＂有效＂的算法，其中＂有效＂的含义我们将在本章的后面解释。有趣的是，已知这一问题在量子计算机上具有有效的算法。经验教训是，对于寻找素因子这项任务，在经典计算机和量子计算机之间似乎存在着差异。这本身就是非常有趣的，并且可能具有更广泛的意义——它表明这种差异可能存在于更广泛的一类计算问题当中，而不仅仅是寻找素因子。通过进一步研究这个特定的问题，有可能辨别出使问题在量子计算机上比经典计算机上更易处理的特征，然后根据这些洞见找到解决其他问题的量子算法。
最后，也是最重要的，学会像计算机科学家一样思考。计算机科学家以与物理学家或其他自然科学家完全不同的方式思考。任何想要深人了解量子计算和量子信息的人都必须学会在有些时候像计算机科学家一样思考；他们必须本能地知道何种技术，以及更重要的是哪些问题是计算机科学家最感兴趣的。
本章的结构如下。在 3.1 节中，我们介绍两种计算模型：图灵机模型和电路模型。图灵机模型将用作我们的基本计算模型。然而，在实践中，我们主要利用电路模型，这是在量子计算的研究中最有用的模型。有了计算模型以后，本章的其余部分将讨论计算的资源需求。 3.2 节首先概述我们感兴趣的计算任务，并讨论一些相关的资源问题。接着概览计算复杂性这一关键概念，该领域研究解决特定计算问题所需的时间和空间要求，并根据求解难度给出对问题的一般性分类。最后，本节以探讨执行计算所需的能量结束。令人惊讶的是，事实证明，只要人们能够使计算可逆，执行计算所需的能量消耗可以几乎为零。我们将解释如何构建可逆计算机，并解释它们对于计算机科学以及量子计算和量子信息都非常重要的一些原因。 3.3 节概述整个计算机科学领域，重点讨论与量子计算和量子信息特别相关的问题。
……算法是独立于任何编程语言之外而存在的概念。 ——高德纳
有一个执行某项任务的算法是什么意思呢？孩提时代，我们都学习过使我们能够将任何两个数字相加的步骤，无论这些数字有多大。这就是算法的一个例子。本节的目标是找到算法这一概念数学上的精确描述。
从历史上看，算法的概念可以追溯到数个世纪以前；本科生都学习过欧几里得两千年前寻找两个正整数的最大公约数的算法。然而，直到 20 世纪 30 年代，现代算法理论和计算理论的
基本概念才由阿隆佐•丘奇，阿兰•图灵和计算机时代的其他先驱引人。这项工作是为了回应伟大的数学家大卫－希尔伯特在 20 世纪早期所提出的巨大挑战。希尔伯特询问是否存在某个算法，原则上可以用于求解所有的数学问题。希尔伯特希望这个问题（它有时被称为可判定性问题〔entscheidungsproblem〕）的答案是肯定的。
令人惊讶的是，希尔伯特问题的答案被证明是否定的：不存在一个算法可以解决所有的数学问题。为了证明这一点，丘奇和图灵必须解决如何使用数学定义刻画当我们使用算法这一直观概念时所表达的意思的深刻问题。通过这样做，他们为现代算法理论奠定了基础，并因此也为现代计算机科学理论奠定了基础。
在本章中，我们使用两种看似不同的方法通往计算理论。第一种方法是由图灵提出的。图灵定义了一类机器，现在称为图灵机，用来刻画执行某项计算任务的算法的概念。在 3.1.1节中，我们描述将图灵机，然后讨论图灵机模型的一些更简单的变体。第二种方法是通过电路计算模型，这种方法十分有用，为我们之后的量子计算机研究做了准备。电路模型在 3.1.2 节中描述。虽然这些计算模型表面上看起来不同，但事实证明它们是等价的。你可能会问，为什么要引入多个计算模型？我们这样做是因为不同的计算模型对解决特定的问题可能会产生不同的见解。思考同一概念的两种（或更多种）方式比一种要好。
图灵机的基本要素如图 3－1 所示。图灵机包含四个主要元素：（a）程序，这十分像普通的计算机；（b）有限状态控制器，其作用类似于精简的微处理器，协调机器的其他运算；（c）纸带，其作用类似于计算机内存；（d）读写头，指向带上当前可读或可写的位置。我们现在更详细地描述这四个元素中的每一个。
图 3－1 图灵机的主要元素。在文中，带上的空白符用＂b＂表示。注意 $\triangleright$ 标记带的左端点 图灵机的有限状态控制器由一组有限的内部状态 $q_{1}, \cdots, q_{m}$ 组成。数字 $m$ 可以变化；事实上，对于足够大的 $m$ ，这本质上不影响机器的能力，因此不失一般性，我们可以假设 $m$ 是某个固定的常数。理解有限状态控制器的最佳方式是把它看作一种协调图灵机运算的微处理器。它提供纸带外的临时存储，以及可以完成机器的所有处理的核心位置。除了状态 $q_{1}, \cdots, q_{m}$ ，还有两个特殊的内部状态，标记为 $q_{\mathrm{s}}$ 和 $q_{\mathrm{h}}$ 。我们分别称它们为起始状态和停止状态。其中的想法是，在
计算开始时，图灵机处于起始状态 $q_{\mathrm{s}}$ 。执行计算会导致图灵机的内部状态发生变化。如果计算完成，图灵机将以状态 $q_{\mathrm{h}}$ 结束，表示机器完成了它的运算。
图灵机的纸带是一维的，可以在一个方向上延伸到无限远。纸带由无限长的纸带格序列组成。我们将纸带格编号为 $0,1,2,3, \cdots$ 。每个纸带格包含一个来自于某个字母表 $\Gamma$ 的符号，其中 $\Gamma$ 包含有限个不同的符号。现在，假设字母表包含四个符号将是方便的，我们用 $0,1, b$（＂空白＂符）和 $\triangleright$（标记带的左端点）表示。开始时，带的左端包含一个 $\triangleright$ 符号和有限个 0 和 1 ，带的其余部分包含空白符。读写头指定图灵机纸带上的某个方格作为机器当前正在访问的方格。
总而言之，机器在有限状态控制器处于状态 $q_{\mathrm{s}}$ 时开始它的运算，此时读写头位于最左端编号为 0 的纸带格上。然后计算根据程序逐步进行，这将在之后定义。如果当前状态是 $q_{\mathrm{h}}$ ，那么计算停止，并且计算的输出是纸带当前的（非空白）内容。
图灵机的程序是形如 $\left\langle q, x, q^{\prime}, x^{\prime}, s\right\rangle$ 的程序行的有限顺序列表。程序行的第一项 $q$ 是来自于机器内部状态集的一个状态。第二项 $x$ 取自可能出现在纸带上的符号组成的字母表 $\Gamma_{\circ}$ 程序的工作方式是在每个机器周期中，图灵机按顺序查看程序行列表，搜索形如 $\langle q, x, \cdot, \cdot, \cdot\rangle$ 的程序行，其中机器当前的内部状态为 $q$ ，带上正在读取的符号是 $x$ 。如果它没有找到这样的程序行，那么机器的内部状态变为 $q_{\mathrm{h}}$ ，且机器停止运行。如果找到了这样程序行，则执行该程序行。程序行的执行包括以下步骤：机器的内部状态更改为 $q^{\prime}$ ；纸带上的符号 $x$ 被符号 $x^{\prime}$ 覆盖，并且读写头向左移动，向右移动，或者保持不动，这分别取决于 $s$ 是 $-1,+1$ 还是 0 。这个规则的唯一例外是，如果带头位于最左端的纸带格，且 $s=-1$ ；在这种情况下带头保持不动。
现在我们已经知道了什么是图灵机，让我们看看如何使用它来计算一个简单的函数。考虑如下图灵机的示例。初始时机器的纸带上是一个二进制数 $x$ ，其后跟着空白符。除了起始状态 $q_{\mathrm{s}}$ 和停止状态 $q_{\mathrm{h}}$ 之外，机器还具有三个内部状态 $q_{1}, ~ q_{2}$ 和 $q_{3}$ 。它的程序包含如下程序行（左侧的数字是为了方便在后面的讨论中引用程序行，其本身不是程序的一部分）：
$$ \begin{aligned} & 1:\left\langle q_{\mathrm{s}}, \triangleright, q_{1}, \triangleright,+1\right\rangle \\ & 2:\left\langle q_{1}, 0, q_{1}, b,+1\right\rangle \\ & 3:\left\langle q_{1}, 1, q_{1}, b,+1\right\rangle \\ & 4:\left\langle q_{1}, b, q_{2}, b,-1\right\rangle \\ & 5:\left\langle q_{2}, b, q_{2}, b,-1\right\rangle \\ & 6:\left\langle q_{2}, \triangleright, q_{3}, \triangleright,+1\right\rangle \\ & 7:\left\langle q_{3}, b, q_{\mathrm{h}}, 1,0\right\rangle \end{aligned} $$
该程序计算的是什么函数呢？初始时机器处于状态 $q_{\mathrm{s}}$ 和最左端的纸带格上，因此第一行被执行，这导致带头向右移动而不改变纸带上写人的内容，但是机器的内部状态变为 $q_{1}$ 。接下来的三行程序确保当机器处于状态 $q_{1}$ 时，如果它在纸带上读取到 0 （第 2 行）或者 1 （第 3 行），带头会继续向右移动，同时使用空白符覆盖带上的内容，并且保持在状态 $q_{1}$ ，直到它到达一个已经包含空白符的纸带格，此时读写头向左移动一个位置，并且内部的状态变为 $q_{2}$（第 4 行）。其后，第 5 行确保带头在读取到空白符的时候保持向左移动而不改变带的内容。这一直持续到带头返回
它的起始点，此时它在纸带上读取到 $\triangleright$ ，将内部状态更改为 $q_{3}$ ，然后向右移动一步（第 6 行）。第 7 行完成程序，仅仅将数字 1 打印到纸带上，然后停止。
前面的分析表明，该程序计算常值函数 $f(x)=1$ 。也就是说，无论在带上输入什么数字，最终都输出数字 1 。更一般地，图灵机可以被当作是计算从非负整数到非负整数的函数；带的初始状态用于表示函数的输人，纸带的最终状态用于表示函数的输出。
似乎我们使用图灵机来计算这个简单的函数已经非常麻烦了。是否可能使用图灵机来构造更复杂的函数？例如，我们能否构造一台机器，使得当用空白符分隔的两个数字 $x$ 和 $y$ 作为纸带上的输入时，它会在纸带上输出和 $x+y$ ？更一般地，使用图灵机可以计算哪类函数？
事实证明，图灵机的计算模型可用于计算各种各样的函数。例如，它可以用于执行所有的基本算术运算，搜索在纸带上表示为比特串的文本，以及许多其他有趣的操作。令人惊讶的是，事实证明图灵机可以用来模拟在现代计算机上执行的所有操作！实际上，根据丘奇和图灵独立提出的论题，图灵机的计算模型完全刻画了使用算法计算函数的概念。这被称为丘奇－图灵论题：
图灵机可计算的函数类完全对应于我们自然地认为可由算法计算的函数类。
丘奇－图灵论题断言了一个严格的数学概念——图灵机可计算的函数——与可由算法计算的函数这一直观概念之间的等价性。此命题的重要性源于它使得现实世界的算法研究成为了严格的数学研究，而这在 1936 年以前是个相当模糊的概念。为了理解这一点的重要性，考虑实分析中连续函数的定义可能会有所帮助。每个孩子都可以告诉你纸上的一条线连续是什么意思，但如何以一个严格的定义来刻画这种直观并不显然。在连续性的现代定义被接受之前，十九世纪的数学家花了很长时间争论各种连续性定义的优点。当进行诸如连续性或可计算性等基本定义时，选择好的定义非常重要，确保一个人的直观想法与精确的数学定义紧密匹配。从这个观点来看，丘奇－图灵论题断言了图灵机的计算模型为计算机科学提供了良好的基础，以一个严格的定义刻画了算法这一直观概念。
先验地，每个我们直观上认为可以由算法计算的函数都可以使用图灵机来计算并不显然。丘奇，图灵和许多其他的学者花了很多时间来收集丘奇－图灵论题成立的证据，六十年来，没有任何相反的证据被找到。然而，未来我们可能会在自然界中发现一个过程，它计算某个函数，而这个函数不能在图灵机上计算。发生这种情况将是极好的，因为我们可以利用这个过程来帮助我们进行以前无法进行的新计算。当然，我们还需要彻底检查可计算性，甚至计算机科学的定义。 习题3.1（自然界中的不可计算过程）我们如何识别出自然界中的某个过程，它能够计算图灵机无法计算的函数？ 习题3.2（图灵编号）证明每个单带图灵机都可以从列表 1，2，3 $\cdots$ 中获得一个编号，使得这个编号唯一地确定其相应的机器。我们将此编号称为相应图灵机的图灵编号。（提示：每个正整数都有一个唯一的素因子分解 $p_{1}^{a_{1}} p_{2}^{a_{2}} \cdots p_{k}^{a_{k}}$ ，其中 $p_{i}$ 是不同的素数，而 $a_{1}, \cdots, a_{k}$ 是非负整数。）
在后面的章节中，我们将看到量子计算机也遵循丘奇－图灵论题。也就是说，量子计算机与图灵机可计算的函数类相同。量子计算机和图灵机之间的区别在于使用它们执行函数计算时的效
率——有些函数可以在量子计算机上更有效地计算，而人们相信这在诸如图灵机之类的经典计算设备上是不可能的。
完整详细地说明图灵机的计算模型可用于构建在计算机编程语言中使用的所有常用概念超出了本书的范围（更多的信息请参阅本章末尾的＂背景资料与延伸阅读＂）。当详细说明算法时，我们通常会使用更高级别的伪代码，而不是显式地说明用于执行该算法的图灵机；基于丘奇－图灵论题，伪代码都可以被转换为图灵机计算模型。我们不会对伪代码给出任何严格的定义。可以把它想象成一个稍微更加形式化一些的英语，或者，如果你愿意，可以把它看作 C＋＋或 BASIC等高级编程语言的粗略版本。伪代码提供了一种表达算法的便捷方式，无需探究图灵机所要求的细枝末节。使用伪代码的示例可以在专题 3.2 中找到；它也在本书的后面用来描述量子算法。
基础的图灵机模型有许多变种。我们可以想象图灵机具有不同种类的纸带。例如，可以考虑双向无限的纸带，或者使用多个维度的纸带进行计算。就目前所知，不可能以物理层面上合理的方式改变图灵模型的某个方面，从而扩展模型可计算的函数类。
作为例子，考虑配备多条纸带的图灵机。为简单起见，我们考虑两条纸带的情况，因为从这个示例到两条纸带以上的推广是显然的。与基础的图灵机一样，双带图灵机具有有限个内部状态 $q_{1}, \cdots, q_{m}$ ，一个起始状态 $q_{\mathrm{s}}$ 和一个停止状态 $q_{\mathrm{h}}$ 。它有两条带，每条带包含一些来自于一个有限的字母表 $\Gamma$ 的符号。像之前一样，假设字母表包含四个符号 $0,1, b$ 以及 $\triangleright$ 是很方便的，其中 $\triangleright$ 标记每条带的左端。该机器有两个读写头，每条纸带一个。双带图灵机和基础图灵机之间的主要区别在于程序。程序行的形式为 $\left\langle q, x_{1}, x_{2}, q^{\prime}, x_{1}^{\prime}, x_{2}^{\prime}, s_{1}, s_{2}\right\rangle$ ，这意味着如果机器的内部状态为 $q$ ，纸带 1 在其当前位置读取 $x_{1}$ ，纸带 2 在当前位置读取 $x_{2}$ ，那么机器的内部状态应更改为 $q^{\prime}, x_{1}$ 被 $x_{1}^{\prime}$ 覆盖，$x_{2}$ 被 $x_{2}^{\prime}$ 覆盖，纸带 1 和纸带 2 分别根据 $s_{1}$ 或 $s_{2}$ 等于 $+1,-1$ 或者 0 来移动。
在何种意义下，基础图灵机和双带图灵机是等价的计算模型？它们在一个计算模型能够模拟另一个的意义下是等价的。假设我们有一个双带图灵机，除了端点标记 $\triangleright$ 之外，它把第一条带上的比特串 $x$ ，两条纸带上其余部分的空白符作为输人。该机器计算函数 $f(x)$ ，其中 $f(x)$ 被定义为图灵机停机后第一条纸带的内容。相当值得注意的是，事实证明，给定一个计算 $f$ 的双带图灵机，存在一个等价的单带图灵机，它也能够计算 $f$ 。我们不会明确地解释如何做到这一点，但基本的想法是单带图灵机使用它的单条纸带存储双带图灵机两条纸带上的内容来模拟双带图灵机。进行这一模拟需要一些计算上的开销，但重要的是原则上它总是可以做到的。事实上，存在一台通用图灵机（见专题 3.1），可以模拟任何其他的图灵机！
图灵机模型的另一个有趣变体是将随机性引人到模型中。例如，假设图灵机可以执行一个程序行，其效果如下：如果内部状态为 $q$ 并且带写头读取 $x$ ，那么投掷一枚无偏的硬币。如果硬币正面朝上，将内部状态改为 $q_{i_{H}}$ ，如果它反面朝上，将内部状态改为 $q_{i_{T}}$ ，其中 $q_{i_{H}}$ 和 $q_{i_{T}}$ 是图灵机的两个内部状态。这样的程序行可以表示为 $\left\langle q, x, q_{i_{H}}, q_{i_{T}}\right\rangle$ 。然而，即使是这个变体也不会从本质上改变图灵机计算模型的能力。不难看出，我们可以在确定型图灵机上通过显式地＂遍历＂与沏拍硬币出现的不同数值对应的所有可能的计算路径来模拟上述算法的效果。当然，这种确定型的模拟可能远不如随机模型有效，但是这里讨论的重点在于，引人随机性到底层模型当中也不会改变可计算的函数类。 习题 3.3 （翻转比特串的图灵机）描述一个图灵机，它以二进制数 $x$ 作为输人，并以相反的顺
序输出 $x$ 的比特。（提示：在这个习题和下个习题中，使用多带图灵机并且／或者除了 $\triangleright, 0,1$ 和空白符之外的符号或许会有所帮助。）
习题3.4（模 2 加法的图灵机）描述一个图灵机，在模 2 意义下把两个二进制数 $x$ 和 $y$ 相加。数字以二进制的形式作为图灵机纸带上的输人，形式为 $x$ 后面跟着一个空白符，然后跟着 $y$ 。如果两者长度不同，那么你可以假设在较短的前面填补了足够多的 0 ，使得两个数具有相同的长度。
让我们回到希尔伯特的可判定性问题，这是计算机科学的创始人最初的灵感。是否存在算法能够判定所有的数学问题？丘奇和图灵证明了这个问题的答案是否定的。在专题 3.2 中，我们解释了图灵对这一显著事实的证明。不可判定性这种现象如今已经远远超出了丘奇和图灵所构造的例子。例如，众所周知，确定两个拓扑空间是否拓扑等价（＂同胚＂）的问题是不可判定的。正如你会在问题 3.4 中证明的那样，存在与动态系统的行为相关的简单问题，它们也是不可判定的。这些例子和其他例子的参考文献会在本章末尾的＂背景资料与延伸阅读＂给出。
除了其固有的价值之外，不可判断性预示着计算机科学，以及量子计算和量子信息中一个备受关注的话题：易于解决的问题与难以解决的问题之间的区别。不可判定性提供了难以解决的问题的终极例子——它们是如此之难，以至于实际上不可能解决。
我们已经将图灵机描述为包含三部分，各部分可能因机器而异——纸带上的初始格局，有限状态控制器的内部状态，以及机器的程序。一个被称为通用图灵机（UTM）的聪明想法允许我们一劳永逸地固定住程序和有限状态控制器，使得带上的初始内容成为机器唯一可以改变的部分。
通用图灵机（见下图）具有以下特性。设 $M$ 为任意的图灵机，令 $T_{M}$ 为与机器 $M$ 关联的图灵编号。然后在如下输入上：$T_{M}$ 的二进制表示后跟着一个空白符，而后在纸带的其余部分上跟着任意的字符串 $x$ ，通用图灵机给出机器 $M$ 在输入 $x$ 上的输出作为它的输出。因此，通用图灵机能够模拟任何其他的图灵机！
通用图灵机在本质上类似于现代可编程计算机，其中计算机采取的动作——＂程序＂——存储在内存当中，类似于存储在通用图灵机的纸带开头的比特串 $T_{M}$ 。程序要处理的数据存储在内存的另一部分当中，类似于通用图灵机中 $x$ 的角色。然后使用一些固定的硬件来运行程序，产生输出。该固定的硬件类似于内部状态和通用图灵机所执行的（固定）程序。
描述通用图灵机的详细结构超出了本书的范围。（虽然勤奋的读者可能会尝试构造。）重点在于这样的机器是存在的，它表明可以使用单个固定的机器来运行任何算法。通用图灵机
的存在也解释了我们早先的关于图灵机中内部状态的数量无关紧要的陈述，因为只要那个数量 $m$ 超过了通用图灵机所需的数量，那么这样的机器就可以用来模拟具有任意数量的内部状态的图灵机。
习题3.5（不含输入的停机问题）证明给定图灵机 $M$ ，不存在算法能够确定当机器的输人是空白带时 $M$ 是否停机。
习题 3.6（概率停机问题）假设我们使用类似于习题3.2中的方案对概率型图灵机进行编号，并且定义概率停机函数 $h_{p}(x)$ 为 1 ，如果机器 $x$ 在输人 $x$ 上以至少 $1 / 2$ 的概率停机；$h_{p}(x)$ 为 0 ，如果机器 $x$ 在输人 $x$ 上以小于 $1 / 2$ 的概率停机。证明不存在概率型图灵机，其对所有的 $x$ 都以严格大于 $1 / 2$ 的概率输出 $h_{p}(x)$ 。 习题3.7（停机神谕）假设我们可以使用一个黑盒，它以非负整数 $x$ 作为输人，然后输出 $h(x)$的值，其中 $h(\cdot)$ 是专题 3.2 中定义的停机函数。这种类型的黑盒有时被称为停机问题的神谕。假设我们有一个普通的图灵机，它增加了调用这个神谕的能力。实现这一目标的一种方法是使用双带图灵机，并向图灵机添加一个额外的程序指令，从而能够调用神谕，并在第二条带上打印出 $h(x)$ 的值，其中 $x$ 是第二条带上当前的内容。显然这个计算模型比传统的图灵机模型更加强大，因为它可以用来计算停机函数。这个计算模型的停机问题是不可判定的吗？也就是说，借助停机问题的神谕帮助的图灵机能否确定带有此神谕的图灵机的程序在特定的输人上是否会停机？
在习题3.2中证明了每个图灵机都可以唯一地关联到列表 $1,2,3, \cdots$ 中的一个数字。为了解决希尔伯特的问题，图灵使用这一编号提出了停机问题：图灵编号为 $x$ 的机器是否在输入为编号 $y$ 时停机？这是一个良定义的和有趣的数学问题。毕竟，我们对我们的算法是否能停止相当感兴趣。然而事实证明，没有算法能够解决停机问题。为了看到这一点，图灵询问是否存在算法来解决一个更特殊的问题：图灵编号为 $x$ 的机器是否在输入为相同的编号 $x$时停机？图灵定义了停机函数，
$$ h(x) \equiv \begin{cases}0 & \text { 如果编号为 } x \text { 的机器在输入 } x \text { 上不停机 } \\ 1 & \text { 如果编号为 } x \text { 的机器在输入 } x \text { 上停机 }\end{cases} $$
如果存在算法能够解决停机问题，那么当然存在算法能够计算 $h(x)$ 。我们将试图通过假设存在这样的算法（用 $\operatorname{HALT}(x)$ 表示）来导出矛盾。考虑计算函数 $\operatorname{TURING}(x)$ 的算法，它的伪代码是
TURING（ x ） $y=\operatorname{HALT}(x)$ if $\mathrm{y}=0$ then 停机 else 永远循环 end if 由于 HALT 是一个合法的程序，TURING 必然也是一个合法的程序，且具有某个图灵编号 $t$ 。根据停机函数的定义，$h(t)=1$ 当且仅当 TURING 在输入 $t$ 上停机。但是通过检查 TURING 的程序，我们发现 TURING 在输入 $t$ 上停机当且仅当 $h(t)=0$ 。因此 $h(t)=1$ 当且仅当 $h(t)=0$ ，矛盾。因此，我们最初假设存在一种计算 $h(x)$ 的算法一定是错的。我们得出结论，没有算法允许我们解决停机问题。
图灵机是非常理想化的计算设备模型。真正的计算机大小是有限的，而对于图灵机我们假定它是一台无限大的计算机。在本节中，我们研究另外一种计算模型，即电路模型。它在计算能力方面与图灵机相当，但对于许多应用来说更加方便和实际。特别地，电路计算模型作为我们对量子计算机研究的准备工作尤其重要。
电路由导线和门组成，它们分别携带信息和执行简单的计算任务。例如，图 3－1 展示了一个简单的电路，它将单比特 $a$ 作为输人。该比特被传递给一个非（NOT）门，非门翻转该比特，把 1 变成 0 ，把 0 变成 1 。非门前后的导线仅仅负责运输比特进出非门；它们可以表示比特在空间中的移动，或者随时间的变动。
图 3－2 在单个输人比特上执行单个 NOT 门的基本电路
更一般地，电路可能包含许多输人和输出比特，许多导线和许多逻辑门。逻辑门是从某些固定的 $k$ 个输人比特到某些固定的 $l$ 个输出比特的函数 $f:{0,1}^{k} \rightarrow{0,1}^{l}$ 。例如，非门是具有一个输人比特和一个输出比特的门，它计算函数 $f(a)=1 \oplus a$ ，其中 $a$ 是单个比特，且 $\oplus$ 是模 2 加法。通常约定电路中不允许循环，以避免可能出现的不稳定性，如图 3－3 所示。我们说这样的电路是无环的，并且我们坚持电路计算模型中的电路是无环的这一惯例。
图 3－3 包含回路的电路可能不稳定，通常在电路计算模型当中是不允许的
还有许多其他基本逻辑门可用于计算。一个部分的列表包括与（AND）门，或（OR）门，异或（XOR）门，与非（NAND）门和或非（NOR）门。这些门中的每一个都有两个比特作为输人，并产生单个比特作为输出。与门输出 1 当且仅当它的两个输人均为 1 。或门输出 1 当且仅当它的输人中至少有一个是 1 。异或门输出其输入的模 2 和。与非门和或非门分别使用与门和或门作用在它们的输人上，而后使用非门作用在前一个门的输出上。这些门的作用如图 3－4 所示。
（a）
（b）
（d）
（e）
（f）$\quad \begin{aligned} & a ŋ 0-a \text { NOR } b= \\ & b- \\ & \end{aligned}$
图 3－4 实现与，或，异或，与非和非门的基本电路
图 3－4 中缺少两个重要的＂门＂，即扇出（FANOUT）门和交叉（CROSSOVER）门。在电路中，我们经常允许比特＂分裂＂，用自身的两个副本代替它自己，这一操作被称为扇出。我们还允许比特交叉，即，两个比特的值互相交换。图 3－4 中缺少的第三个操作——并不真的是逻辑门 ——是允许准备额外的辅助比特或工作比特，以便在计算中有额外的工作空间。
这些简单的电路元件可以放在一起以执行各种各样的计算。下面我们将展示这些元件可用于计算任何函数。与此同时，让我们看一个简单的电路示例，该电路使用的是跟世界各地教给学龄儿童的完全相同的算法来相加两个 $n$ 比特整数。该电路中的基本元件是一个被称为半加法器的更小的电路，如图 3－5 所示。半加法器把两个比特 $x$ 和 $y$ 作为输人，并输出它们的模 2 加和 $x \oplus y$以及一个进位，如果 $x$ 和 $y$ 都是 1 ，则进位为 1 ，否则为 0 。
图 3－5 半加法器电路。当 $x$ 和 $y$ 都为 1 时，进位 $c$ 设置为 1 ，否则为 0
可以使用两个级联的半加法器来构造一个全加法器，如图 3－6 所示。全加法器把三个比特 $x, y$ 和 $c$ 作为输人。比特 $x$ 和 $y$ 应该看做是要相加的数据，而 $c$ 则来自较早计算的进位。电路输出两个比特。一个输出比特是所有三个输人比特的模 2 加和 $x \oplus y \oplus c$ ，第二个输出比特 $c^{\prime}$ 是进位，如果两个或多个输入为 1 ，那么它设置为 1 ，否则为 0 。
图 3－6 全加法器 通过将许多这些全加法器组合在一起，我们得到一个相加两个 $n$ 比特整数的电路，图 3－7 显示了 $n=3$ 的情况。
我们之前声称只需几个固定的门就可以用来计算任意的函数 $f:{0,1}^{n} \rightarrow{0,1}^{m}$ 。我们现在将对具有 $n$ 个输入比特和单个输出比特的函数 $f:{0,1}^{n} \rightarrow{0,1}$ 这一简化情况进行证明。这
样的函数被称为布尔函数，相应的电路就是布尔电路。一般的通用性证明可由布尔函数这一特殊情况立即得出。证明通过对 $n$ 的归纳进行。对于 $n=1$ ，有四种可能的函数：恒等函数，它的电路由单根导线组成；位翻转函数，可由单个非门实现；使用 0 来替换输人比特的函数，可以通过将输人与一个初始化为 0 的工作比特进行与操作得到；以及使用 1 来替换输人的函数，可以通过将输人和一个初始化为 1 的工作比特进行或操作得到。
图 3－7 两个三比特整数 $x=x_{2} x_{1} x_{0}$ 和 $y=y_{2} y_{1} y_{0}$ 的加法电路，使用教给学龄儿童的基本算法 为了完成归纳，假设任意 $n$ 比特函数可以由电路计算，并且令 $f$ 是 $n+1$ 个比特上的函数。定义 $n$ 比特函数 $f_{0}$ 和 $f_{1}$ 为 $f_{0}\left(x_{1}, \cdots, x_{n}\right) \equiv f\left(0, x_{1}, \cdots, x_{n}\right)$ 和 $f_{1}\left(x_{1}, \cdots, x_{n}\right) \equiv f\left(1, x_{1}, \cdots, x_{n}\right)$ 。它们都是 $n$ 比特函数，因此根据归纳假设，存在计算这些函数的电路。
现在设计一个计算 $f$ 的电路成了一件容易的事。该电路在最后 $n$ 比特的输人上计算 $f_{0}$ 和 $f_{1}$ 。然后，它根据输人的第一个比特是 0 还是 1 来输出合适的答案。一个执行此操作的电路如图 3－8所示。这完成了归纳。
图 3－8 计算 $n+1$ 个比特上的任意函数 $f$ 的电路，根据归纳假设存在计算 $n$ 比特函数 $f_{0}$ 和 $f_{1}$ 的电路 从上述通用电路构造中可以识别出 5 个要素：（1）导线，其保持比特的状态；（2）制备为标准态的辅助比特，其用于证明中 $n=1$ 的情况；（3）扇出运算，其以单个比特作为输人，输出该比特的两个副本；（4）交叉运算，它交换两个比特的值；（5）与门，异或门和非门。在第4章中，我们将以类似于经典电路的方式来定义量子电路计算模型。值得注意的是，当扩展到量子的情况时，这五要素中的许多元素都提出了一些有趣的挑战：构造出保持量子比特的状态的良好量子导线这件事并不显然；即使在原则上，根据不可克隆定理（正如 1.3 .5 节所解释的），扇出操作也不能在量子力学中以一种直接的方式实现；并且由于与门和异或门是不可逆的，因此不能以直接的方式实现为一个西量子门。在定义量子电路计算模型时还有许多需要思考的地方！
习题 3.8 （NAND 的通用性）假设可以使用导线，辅助比特和扇出，证明与非门可以用来模拟与门，异或门和非门。
让我们从我们对量子电路简短的讨论中回到经典电路的性质上。我们之前声称图灵机模型和电路计算模型等价。在什么意义下我们认为这两个模型是等价的呢？从表面上看，这两个模型看起来完全不同。图灵机无界的特性使它们更有助于抽象地概括算法的含义，而电路更接近于刻画实际的物理计算机是什么。
通过引人一致电路族的概念可以联系这两个模型。电路族由一组电路 $\left\{C_{n}\right\}$ 组成，它们由正整数 $n$ 来索引。电路 $\left\{C_{n}\right\}$ 具有 $n$ 个输人比特，并且可能具有任意有限个额外的工作比特，以及输出比特。在长度最多为 $n$ 个比特的输人 $x$ 上，电路 $C_{n}$ 的输出被记为 $C_{n}(x)$ 。我们要求电路是一致的，也就是说，如果 $m < n$ 且 $x$ 的长度最多是 $m$ 比特，那么 $C_{m}(x)=C_{n}(x)$ 。电路族 $\left\{C_{n}\right\}$计算的函数是函数 $C(\cdot)$ ，使得如果 $x$ 的长度是 $n$ 个比特，那么 $C(x)=C_{n}(x)$ 。例如，考虑对 $n$位数进行平方的电路 $C_{n}$ 。它定义了电路族 $\left\{C_{n}\right\}$ ，计算函数 $C(x)=x^{2}$ ，其中 $x$ 是任意正整数。
然而，考虑不受限制的电路族是不够的。在实际当中，我们需要一个算法来构建电路。实际上，如果我们不对电路族进行任何限制，那么计算所有种类的函数，甚至那些我们在合理的计算模型中预期不能够计算的函数，便成为了可能。例如，令 $h_{n}(x)$ 表示限制 $x$ 的长度为 $n$ 个比特的停机函数。因此 $h_{n}$ 是一个从 $n$ 个比特到 1 个比特的函数，而我们已经证明了存在计算 $h_{n}(\cdot)$ 的电路 $C_{n}$ 。因此电路族 $\left\{C_{n}\right\}$ 计算停机函数！然而，阻止我们使用这个电路族来解决停机问题的原因是我们没有指定一个允许我们对所有的 $n$ 构造电路 $\left\{C_{n}\right\}$ 的算法。添加此要求便得到了一致电路族的概念。
也就是说，电路族 $\left\{C_{n}\right\}$ 被称为是一致电路族，如果存在某个运行在图灵机上的算法，其在输人 $n$ 上，生成 $C_{n}$ 的一个描述。也就是说，该算法的输出描述了电路 $C_{n}$ 中有哪些门，这些门如何连接在一起组成一个电路，电路所需的辅助比特，扇出和交叉运算，以及应该从电路的哪里读取输出。例如，我们前面描述的用于对 $n$ 位数进行平方的电路族当然是一个一致电路族，因为存在一个算法，当给定 $n$ 时，其输出对 $n$ 位数进行平方时所需的电路的描述。你可以将此算法视为工程师能够对任意的 $n$ 生成电路的描述（并由此构建电路）的工具。相反地，不一致的电路族被称为非一致电路族。没有算法可以对任意的 $n$ 构建此电路，这阻止了我们的工程师构建电路来计算诸如停机函数之类的函数。
直观上，一致电路族是可以由某个合理的算法生成的电路族。可以证明，一致电路族可计算的函数类与图灵机可计算的函数类完全相同。由于这种一致性的限制，图灵机计算模型中的结论通常可以直接翻译为电路计算模型的结论，反之亦然。之后我们对量子电路计算模型中的一致性问题给予了类似的关注。