第 8 章图灵机导论

从自动机到一般计算：图灵机、扩展模型与 Church–Turing 观点

Source scope
主要依据教材第 8 章：中文印刷页 215–253，对应 PDF p.228–266 前后。教材从“计算机不能解答的问题”切入，随后定义图灵机并讨论程序设计技巧、扩展模型、受限模型及与真实计算机的模拟关系。

1 0. 为什么要引入图灵机

DFA 只有有限记忆；PDA 有一个栈，但仍受结构限制。为了讨论“任何算法都能不能做”，需要一个足够通用又足够简单的数学模型。

图灵机（Turing machine, TM）提供：

可无限延伸的带；
一个读写头；
有限状态控制器；
每一步读、写、移动。

它既简单到可以严格分析，又强大到能模拟通常意义上的程序。

2 1. 从不可解问题的直觉开始

教材用类似 hello, world 程序的例子说明：若存在一个万能程序，能判断任意程序是否会打印某输出，就可能通过“把程序当数据输入自己”构造悖论。

这先建立一个重要思想：

有些问题的困难不是“算法还没找到”，而是根本不存在算法。

第 9 章将正式证明。

3 2. 图灵机的定义

一种标准确定型图灵机写成

\[ M=(Q,\Sigma,\Gamma,\delta,q_0,B,F), \]

其中：

\(Q\)：状态集合；
\(\Sigma\)：输入字母表；
\(\Gamma\)：带字母表，\(\Sigma\subseteq\Gamma\)；
\(B\in\Gamma\)：空白符；
\(q_0\)：初态；
\(F\)：接受状态集合；
转移函数通常形如 \[ \delta:Q\times\Gamma\to Q\times\Gamma\times\{L,R\}. \]

一个转移

\[ \delta(q,X)=(p,Y,R) \]

表示：读到 \(X\) 时写成 \(Y\)，状态变为 \(p\)，读写头右移一格。

4 3. 瞬时描述与一步计算

图灵机配置必须记录：

当前状态；
整条带上非空白部分；
读写头位置。

常写成

\[ \alpha q\beta, \]

其中状态符号 \(q\) 放在当前扫描符号之前。

一步计算记作

\[ I\vdash_M J, \]

多步记作

\[ I\vdash_M^*J. \]

5 4. 图灵机的语言与停机

若输入 \(w\) 使机器最终进入接受状态，则 \(w\in L(M)\)。

需要区分三种可能：

接受；
拒绝并停机；
永不停止。

这一区别导致：

可识别/递归可枚举语言：成员输入最终接受；非成员可能拒绝，也可能不停；
可判定/递归语言：对每个输入都最终停机，并给出接受或拒绝。

第 9 章会系统化这一区分。

6 5. 图灵机程序设计技术

6.1 5.1 在状态中存储有限信息

状态可以保存有限控制信息，例如：

当前正在处理第几阶段；
曾经见到的某个有限类别；
一个有限标志位。

不能用状态保存无界数据；无界数据必须写在带上。

6.2 5.2 多道（multiple tracks）

把一个带单元看成若干“轨道”的笛卡尔积，可以同时保存：

原输入；
标记位；
辅助工作信息。

多道只是符号重编码，不增强计算能力。

6.3 5.3 子程序

可以把一组状态看成模块：进入某入口状态，完成某任务，再从指定出口返回。

这让图灵机设计更像程序，而不是逐箭头拼接。

7 6. 基本图灵机的扩展

7.1 6.1 多带图灵机

多带 TM 有多个独立带和读写头。一步可同时读取、写入并移动各带头。

它通常更方便、更快，但不增加可计算语言集合。

7.2 6.2 单带与多带等价

可用单带把多条带编码为若干分区，并记录每个虚拟读写头的位置。一次多带步骤可由单带若干扫描模拟。

因此：

\[ \text{single-tape TM}\equiv\text{multi-tape TM} \]

就可计算能力而言相同。

7.3 6.3 非确定型图灵机

NTM 在某配置可有多个后继。接受定义为：存在一条计算分支接受。

与 NFA 类似，但更强大；然而在“可计算什么语言”层面：

\[ \boxed{\text{NTM}\equiv\text{DTM}}. \]

确定型 TM 可系统枚举/模拟非确定计算树。

注意：第 10 章讨论复杂度时，确定与非确定模型虽然在可计算性上等价，但时间复杂度可能差异巨大。

8 7. 受限图灵机

教材展示若干看似更弱的模型仍可模拟一般 TM。

8.1 7.1 半无限带图灵机

带只有一个方向无限延伸。可把原双向带编码到单向带，例如交错存储原点左侧和右侧单元。

8.2 7.2 多栈机

两个栈可以模拟一条双向带：

一个栈保存读写头左侧内容；
一个栈保存当前位置及右侧内容。

8.3 7.3 计数器机

计数器只能增、减和测试零。通过编码与多个计数器，也能获得通用计算能力。

这类等价结果支撑 Church–Turing 观点：很多自然提出的“机械计算模型”最终得到相同的可计算函数集合。

9 8. 图灵机与真实计算机

9.1 8.1 计算机模拟图灵机

真实程序可以保存带的有限已访问部分、当前状态和头位置，因此能模拟 TM。

9.2 8.2 图灵机模拟计算机

反过来，TM 可以编码：

存储器；
指令；
程序计数器；
寄存器。

因此一般程序也可由 TM 模拟。

9.3 8.3 Church–Turing 论题

Church–Turing 论题不是一个数学定理，而是关于“有效可计算”的经验性原则：

凡是通常意义上可由机械算法计算的函数，都可以由图灵机计算。

10 9. 常见错误

把“带无限”误解为“某一步可使用无限空间”；任意有限时间只访问有限单元；
忘记 TM 可以覆写输入；
把“拒绝”与“永不停止”混为一谈；
认为多带 TM 能计算单带 TM 不能计算的语言；
认为 NTM 在可计算性层面比 DTM 更强；
把 Church–Turing 论题写成已证明的形式定理。

11 10. 本章知识地图

DFA < PDA < TM   (表达能力逐步增强)

TM
├─ single tape ≡ multi-tape
├─ deterministic ≡ nondeterministic  [computability]
├─ semi-infinite tape ≡ standard TM
├─ multi-stack / counter variants ≡ TM
└─ model for general algorithmic computation