第二章：计算模型

计算模型规定状态表示、基本操作和输入访问方式。upper bound 必须在某个模型中实现；lower bound 也只能排除该模型允许的算法。

配置与转移

顺序计算模型通常可由配置集合 $C$ 、初始配置映射和转移关系描述：

c_0(x)\to c_1\to c_2\to\cdots.

确定性模型中，每个非终止配置至多有一个后继；非确定性模型允许多个后继，并按“存在接受路径”定义接受。随机模型为转移附加概率；量子模型则在线性空间中演化振幅。

时间通常计算转移次数，空间计算运行过程中可变工作存储的最大规模。不同模型的单步能力不同，直接比较步数前需要先给出模拟。

有限自动机

DFA 的配置只包含当前状态和输入位置。状态数与输入长度无关，因此无法保存无界计数。DFA 识别的 language 正是 regular language。

Myhill–Nerode 定理给出模型无关的刻画。定义

x\equiv_L y \iff \forall z,\; xz\in L\Leftrightarrow yz\in L.

$L$ regular 当且仅当 $\equiv_L$ 的等价类数量有限；最小 DFA 的状态数等于等价类数。该定理同时提供 upper bound 和 lower bound 方法：构造有限状态分类可得自动机，构造大量可区分前缀可得状态数下界。

NFA 允许一组可能状态，但在可识别 language 上与 DFA 等价。subset construction 可产生 $2^m$ 个 DFA 状态，说明表达简洁性与计算能力需要分开讨论。

栈与上下文无关计算

nondeterministic pushdown automaton 在有限控制之外增加一个无界栈，可识别 context-free language。栈支持嵌套结构，但不能随机访问先前内容；deterministic PDA 只能识别其中的真子类。

CFG、PDA 和解析算法之间存在不同层次：

CFG 描述生成结构；
PDA 描述识别模型；
CYK 等算法在 RAM/TM 上分析该结构；
grammar size、parse time 和 ambiguity 是不同资源。

自动机与文法在编译器中仍有直接用途，但其理论价值还在于展示：增加一种受限存储后，计算能力和描述复杂度怎样变化。

图灵机

多带确定性图灵机包含有限控制、有限条无限纸带和读写头。它的基本操作很弱，但能表达任意有限描述的离散算法。

不同常见变体在可计算性上等价：

单带与多带；
只向一侧无限与双向无限纸带；
不同有限字母表；
图灵机与 $\lambda$ calculus、递归函数等。

等价不表示资源完全相同。多带机运行 $t(n)$ 步可以由单带机在约 $O(t(n)^2)$ 时间模拟；这对“是否可计算”无影响，却可能影响细粒度时间界。

universal Turing machine 接收 $\langle M,x\rangle$ 并模拟机器 $M$ 。程序与数据采用同一编码，是不可判定性和通用计算的基础。

Word-RAM

算法分析更常采用 word-RAM。字长通常设为 $w=\Theta(\log n)$ ，从而能够在一个 word 中存储输入地址，并把 word 上的加减、位运算、比较和随机访问计为 $O(1)$ 。

模型必须列出允许操作。若把任意长度整数乘法、floor 或任意查表都当作单位操作，可能在一步中隐藏大量计算。transdichotomous model 用 $w\ge\log n$ 将机器字长与输入规模关联，适合整数算法和数据结构。

多项式时间图灵机与合理 word-RAM 通常能以多项式开销相互模拟，因此 $\mathsf P$ 等粗粒度类较稳健。具体的 $n\log n$ 、 $n^2$ 结论则仍依赖模型。

Boolean circuit

Boolean circuit 是有向无环图，输入节点为变量，内部节点为 AND、OR、NOT 等 gate，输出节点给出函数值。主要资源是：

size：gate 数量；
depth：最长输入到输出路径；
fan-in：每个 gate 的输入数；
uniformity：不同输入长度的线路族能否由统一算法生成。

线路是非一致模型：每个输入长度 $n$ 可以使用独立线路 $C_n$ 。若不要求 uniformity，线路描述本身可以携带关于长度 $n$ 的辅助信息。

depth 表示并行时间的结构上界，size 表示总工作量。二者之间不存在自动等价关系。

通信协议

在 two-party communication model 中，Alice 持有 $x$ ，Bob 持有 $y$ ，双方计算 $f(x,y)$ 。本地计算通常免费，只统计交换 bit 数。

该模型删除了单机计算成本，只保留输入分散造成的信息约束。它既能研究分布式问题，也能通过 communication lower bound 推导 streaming、data structure 和 circuit lower bound。

查询模型

查询模型允许算法通过 oracle 读取输入位置，只统计查询次数。本地计算免费。decision tree 是经典确定性形式；随机和量子查询模型改变选择下一次查询的方式。

查询 lower bound 排除的是“少看输入”的算法，不能直接推出 RAM 时间下界，因为 RAM 算法还可能花费大量本地计算。但它常提供一个干净的必要条件。

量子线路

量子线路在 qubit 状态上施加 unitary gate，最后进行 measurement。线路演化必须保持范数，并遵守局部 gate 和测量规则。

量子模型不是允许同时读取所有答案的非确定性模型。算法需要设计振幅干涉，使正确答案的测量概率增大；测量只能产生一个经典结果。

量子复杂度同样区分 uniform circuit、size、depth、query 和 error probability。第十二章将进一步讨论。

模型选择

选择模型时应匹配待研究限制：

研究可计算性：图灵机提供稳定基准；
分析普通算法：word-RAM 更接近实现；
分析并行性：circuit depth 或 PRAM；
分析数据分散：communication protocol；
分析输入访问：query model；
分析量子优势：quantum circuit 或 quantum query。

lower bound 越依赖受限模型，越需要说明哪些操作被排除。模型更强时，结论通常更有一般性，但证明也更困难。

本章自测

NFA 与 DFA 计算能力相同，为什么 NFA 仍可能指数级更简洁？
图灵机变体的可计算性等价为何不能直接推出相同时间复杂度？
word-RAM 将字长设为 $\Theta(\log n)$ 的作用是什么？
非一致 circuit family 可以包含哪类统一算法没有的附加信息？
communication lower bound 为什么忽略双方的本地计算？

第二章：计算模型 ​

配置与转移 ​

有限自动机 ​

栈与上下文无关计算 ​

图灵机 ​

Word-RAM ​

Boolean circuit ​

通信协议 ​

查询模型 ​

量子线路 ​

模型选择 ​

本章自测 ​