图灵机图灵机像一台只有极少指令的机器它包括一条无限长的纸带类似无限长数组一个搭在纸带上的读写头类似当前指针一组状态类似程序当前运行到的逻辑分支一张状态转移表。每一步图灵机只看两个东西当前状态和当前格子里的符号。然后它根据状态转移表决定写什么符号、切换到哪个状态、读写头往左还是往右移动。如果写成转移规则大概是δ(q,a)(q′,b,D)δ(q,a)(q′,b,D)意思是如果当前处于状态 qq读到符号 aa那么进入状态 q′q′把当前格子写成 bb然后按照方向 DD 移动。这看起来非常原始但正是这种原始性让它适合作为复杂度理论的地基。复杂度理论关心的不是某个 Python 函数在你的电脑上跑了几秒而是是否存在一种计算过程能在某个资源上界内解决某个问题。图灵机就是用来严谨表达“计算过程”的。字母表、字符串和语言字母表 ΣΣ 是一个有限符号集合例如 {0,1}{0,1} 或 {a,b}{a,b}。所有由这些符号组成的有限字符串构成 Σ∗Σ∗。一个语言 LL 就是 Σ∗Σ∗ 的某个子集。换句话说L⊆Σ∗L⊆Σ∗在复杂度理论里判定问题通常会被转化成语言。这其实就是把“问题”写成了“字符串集合”。例如判定问题“这个二进制字符串里是否至少有一个 1”可以对应到语言L{w∈{0,1}∗∣w 中至少有一个 1}L{w∈{0,1}∗∣w 中至少有一个 1}如果一个字符串属于这个集合答案就是“是”如果不属于答案就是“否”。一个最小例子判断字符串里有没有 1考虑判定问题给定一个 {0,1}∗{0,1}∗ 上的字符串它是否至少包含一个1对应的语言是L{w∈{0,1}∗∣w 中至少有一个 1}L{w∈{0,1}∗∣w 中至少有一个 1}例如00100和1属于 LL00000和空串 εε 不属于 LL。用高级语言写核心逻辑是这样的def has_one(s):for ch in s:if ch 1:return Truereturn False现在用图灵机实现同样的逻辑。输入字母表取Σ{0,1}Σ{0,1}纸带字母表取Γ{0,1,_}Γ{0,1,_}其中_表示空白符。状态集取q0q0​起始状态正在向右扫描寻找1qaccqacc​接受状态停机qrejqrej​拒绝状态停机。转移规则 δδ 如下当前状态读入符号写入符号新状态移动方向q0q0​00q0q0​Rq0q0​11qaccqacc​-q0q0​__qrejqrej​-这里的-表示接受或拒绝后立即停机移动方向已经不重要。工作过程是从纸带最左端开始读写头对准输入的第一个字符若读到0不做修改向右一格保持状态 q0q0​若读到1进入接受状态 qaccqacc​ 并停机若读到空白符_说明已经扫描完整个输入且没有发现1进入拒绝状态 qrejqrej​ 并停机。如果输入长度是 nn这台机器最多扫描 nn 个非空白符号然后可能再看一个空白符。因此总步数最多是 n1n1时间复杂度为 O(n)O(n)。这个例子展示了一个简单的判定问题可以严格用图灵机的状态和转移表刻画从而为“存在一台 O(n)O(n) 时间的机器”这样的复杂度论断提供形式化基础。ConfigurationConfiguration 指的是机器在某一瞬间的完整状态。对普通图灵机来说一个 configuration 至少包含当前状态纸带上的内容读写头所在位置。可以把它想象成程序运行时的一张快照。比如某一刻纸带是B a a b b B^并且机器当前处于状态 p0p0​那么这就是一个 configuration。整个计算过程可以写成一串 configuration 的变化K0→K1→K2→⋯K0​→K1​→K2​→⋯这件事后面非常重要。因为我们会用 configuration 来定义时间、空间以及把非确定性计算转化成图上的可达性问题。多带图灵机最基础的图灵机只有一条纸带。输入、中间结果、辅助标记都挤在这一条纸带上。这就像写程序时只给你一个数组和一个指针。理论上已经可以写出任何程序但很多算法描述起来会特别别扭。例如判断一个字符串是否是“连续多个字符 a 连续同样多个字符 b”我们要识别L{anbn∣n≥1}L{anbn∣n≥1}单带图灵机的朴素做法是“配对标记”找一个还没有匹配的a标记掉向右找一个还没有匹配的b标记掉再回到左边找下一个a重复这个过程。读写头会在纸带上来回跑。不是问题本身很难而是单带模型太笨。多带图灵机k-tape Turing machine更像真实程序。一个多带图灵机有 kk 条纸带每条纸带都有自己的读写头。可以把它想成Tape 1: 初始输入 工作区 1Tape 2: 工作区 2Tape 3: 工作区 3...这就更接近我们平时写程序的感觉输入数组、临时数组、计数器、缓冲区各自分开。用两带图灵机识别 anbnanbn 就自然很多第一条带从左到右扫描输入每看到一个a就在第二条带写一个x开始看到b后每看到一个b就在第二条带消掉一个x如果输入结束时刚好消完接受如果a多了、b多了或者中间格式乱了拒绝。用朴素单带配对标记算法时间是 O(n2)O(n2)用多带模型可以很自然地做到 O(n)O(n)。既然单带和多带会影响时间那为什么复杂度理论仍然敢用图灵机定义 P、NP、PSPACE 这些类原因是这些大类很粗它们通常只关心“多项式”还是“指数级”这样的尺度而不是 nn、nlog⁡nnlogn、n2n2 之间的精细差别。多带图灵机可以被单带图灵机模拟。模拟可能带来多项式时间损失但不会把多项式时间变成指数时间。因此对于 P、NP、PSPACE 这种大粒度复杂度类单带、多带、合理的 RAM 模型之间通常不会改变本质结论。所以我们可以这样理解图灵机适合做数学定义和证明多带图灵机适合描述算法真实编程语言适合工程实现他们都是合理模型都适用 P、NP、PSPACE 这些大类。时间复杂度类有了图灵机和 configuration我们可以正式定义“时间”。对一台判定语言的图灵机来说时间复杂度不是只看某个输入上最短的接受路径而是要看它在所有长度为 nn 的输入上是否都能被某个函数上界控制。更具体地说一台确定性机器在输入 xx 上运行了多少步才停机这就是它在 xx 上的运行时间。若对所有长度为 nn 的输入它都能在 O(f(n))O(f(n)) 步内停机并给出正确接受/拒绝那么我们说它在 O(f(n))O(f(n)) 时间内判定这个语言。确定性和非确定性确定性机器的每一步最多只有一个选择。给定当前状态和当前读到的符号下一步是唯一的。之前的例子都是确定性的。非确定性机器则允许在某些状态下有多个可能的下一步path 1/state -- path 2\path 3注意这里的“多个选择”不是无限多个选择。标准非确定性图灵机的转移规则仍然是有限描述的所以每一步的分支数是有限的。只是经过很多步之后整棵计算树可能有指数多条路径。非确定性机器的接受规则是只要存在至少一条计算路径最终接受那么输入就被接受如果没有任何接受路径那么输入被拒绝。这正是 NP 这个概念的底层理论表达非确定性机器可以“猜”一条好路径然后在多项式时间内验证它。DTIME 和 NTIMEDTIME(f)DTIME(f) 表示这样一类语言存在一台确定性图灵机 MM使得对所有输入 xx机器都在 O(f(∣x∣))O(f(∣x∣)) 时间内停机并且x∈L⟺M(x) acceptsx∈L⟺M(x) accepts也就是说语言 LL 可以被确定性算法在 O(f(n))O(f(n)) 时间内判定。NTIME(f)NTIME(f) 表示这样一类语言存在一台非确定性图灵机 MM使得对所有长度为 nn 的输入所有计算分支都在 O(f(n))O(f(n)) 时间内停机并且x∈L⟺存在至少一条计算路径接受 xx∈L⟺存在至少一条计算路径接受 x也就是说语言 LL 可以被非确定性算法在 O(f(n))O(f(n)) 时间内判定。