经典计算理论与计算复杂度解析

# 经典计算理论与计算复杂度解析 ## 1. 经典计算理论基础 ### 1.1 计算与算法的基本概念 计算理论旨在回答关于计算的基本问题，如什么是计算、什么是算法，以及计算的局限性，包括哪些问题是可计算的，完成特定计算任务需要哪些资源。直观上，算法是为计算函数而执行的一系列独立的、逐步的操作。算法计算通过有限步骤（即有限时间）将有限输入（计算开始时给定）转换为有限输出（计算结束时可用）。 ### 1.2 计算理论的历史发展 算法的概念可追溯到古代，但现代概念在20世纪30年代由哥德尔（以递归函数形式）、丘奇（λ - 演算）和图灵（图灵机）正式提出，以回应希尔伯特的猜想，即任何数学命题都可以通过机械逻辑方法判定（证明为真或假）。 ### 1.3 计算资源与复杂度理论 构建计算模型（如图灵机）后，关键问题是执行特定计算任务所需的资源。首先要了解哪些计算任务是可能的，这属于可计算性理论的范畴；其次要确定完成给定计算问题的能力限制。复杂度理论的主要任务是根据计算问题的“难度”对其进行分类，并证明给定问题属于某个复杂度类。计算复杂度为解决给定任务的最佳算法所需的时间和空间资源提供了下限，这与算法设计相辅相成，因为最佳算法可能未知。 ## 2. 图灵机：计算的基本模型 ### 2.1 图灵机的结构 图灵机有四个基本元素： 1. 一维、无限长的可擦除磁带，分为单元格，每个单元格可存储一个符号。 2. 读写头，能在当前位置读写一个符号，并可在磁带上左右移动。 3. 有限状态控制器，协调机器的操作，有有限数量的可用状态。 4. 转移表或程序，根据当前状态和磁带上当前位置的符号，指定新状态和读写头的下一个动作。 ### 2.2 图灵机的工作原理 图灵机总是从初始状态 $q_s$ 开始，读写头位于最左边的单元格 $i = 0$，磁带上包含有限数量的非空白符号（输入）。计算根据转移表逐步进行。在每个计算步骤中，读写头从当前单元格读取符号 $x$，然后根据这个读取结果和当前内部状态 $q$，程序指示： 1. 新的内部状态 $q_0$。 2. 要写入当前单元格的新符号 $x_0$。 3. 读写头的移动 $s$，可以是 $s = +1$（向右移动一个单元格）、$s = -1$（向左移动）或 $s = 0$（静止）。 ### 2.3 图灵机的计算结果 计算可能有四种结果： 1. 图灵机无限循环，不停止。 2. 图灵机试图从单元格 $i = 0$ 向左移动，停止并失败（即输出未定义）。 3. 对 $(q, x)$ 不在指令列表中（即指令不适用），图灵机停止并失败。 4. 图灵机到达停止状态 $q_h$，计算成功，输出由非空白磁带内容给出。 ### 2.4 图灵机的示例：整数加法 以两个非负整数的加法为例，使用一元数字系统，其中数字 $n$ 由包含一个符号（如“1”）重复 $n$ 次的字符串表示。程序如下： ```plaintext 1 : <qs, b; q1, b, +1> 2 : <q1, 1; q1, 1, +1> 3 : <q1, b; q2, 1, +1> 4 : <q2, 1; q2, 1, +1> 5 : <q2, b; q3, b, -1> 6 : <q3, 1; qh, b, 0> ``` 计算过程如下： 1. 初始状态为 $q_s$，读写头从最左边单元格 $i = 0$ 读取空白，执行程序行 1，状态变为 $q_1$，读写头向右移动。 2. 在接下来的 $m$ 个周期中，图灵机执行行 2，读写头移动通过包含整数 $m$ 的单元格。 3. 分隔输入整数的空白变为 1，内部状态变为 $q_2$（行 3）。 4. 读写头继续向右移动（行 4），直到到达空白单元格（单元格 $i = m + n + 2$）。 5. 内部状态变为 $q_3$，读写头向左移动一个单元格（行 5）。 6. 单元格 $i = m + n + 1$ 的内容变为空白，图灵机停止（行 6）。输出是包含 $m + n$ 个非空白符号“1”的字符串。 ### 2.5 图灵机的通用性与可计算性 图灵机模型可以计算更复杂的函数，实际上，它可以模拟现代计算机执行的所有计算操作。可以证明，使用图灵机可计算的函数类等同于其他为定义可计算性而引入的函数类，如哥德尔定义的递归函数和丘奇发明的 λ - 演算。其他计算模型（如电路模型）也被证明与图灵机模型等价。这表明算法实际上就是图灵机所实现的内容，即一个函数是可计算的，当且仅当它可以由图灵机解决，这就是丘奇 - 图灵论题。 ### 2.6 图灵机的变体与通用图灵机 图灵机有不同的变体，如配备多磁带的图灵机，也可以在模型中引入随机性。所有这些计算模型在不同类型的机器可以相互模拟的意义上是等价的，尽管可能会有一些计算开销。每个图灵机 $T$ 可以由一个二进制数 $d[T]$（称为图灵机 $T$ 的图灵数）唯一指定。通用图灵机 $U$ 具有这样的性质：在输入 $d[T]$ 后跟任何有限符号串 $x$（用空白分隔）时，它给出与图灵机 $T$ 在输入 $x$ 时相同的输出，即 $U(d[T], x) = T(x)$。 ### 2.7 图灵机与停机问题 图灵利用这些概念解决了希尔伯特的问题。考虑这样一个问题：具有图灵数 $d[T]$ 的图灵机 $T$ 在以 $d[T]$ 作为输入时是否会停止？假设存在一个算法可以解决这