Lesson 66: 图灵机 aⁿbⁿ 模拟器

练习任务

难度：中

用 C 语言实现一个图灵机模拟器，识别语言 L = {aⁿbⁿ | n ≥ 1}。你需要完成五个函数：

init_tape() — 初始化纸带：用 BLANK 填充整条纸带，再复制输入字符串
print_tape() — 打印纸带：显示当前纸带内容、读写头位置和当前状态
step() — 单步转移：查转移表，执行一次读写→移动→换状态
run() — 运行模拟：驱动整台图灵机，逐步打印，判定接受/拒绝
main() — 主流程：用 "aaabbb"（接受）和 "aab"（拒绝）两个测试串验证

转移表 TRANSITION[state][symbol] 已完整提供，你只需查表使用，无需自己设计转移规则。

本课共有 2 组测试用例：

输入 "aaabbb" → 输出包含 "ACCEPT"
输入 "aab"    → 输出包含 "REJECT"

提示：图灵机的核心是"查表驱动"——step() 中只需三行关键代码：查符号索引 → 查转移表 → 写符号/移头/换状态。不要用 if/else 硬编码转移逻辑。run() 的循环条件是什么？什么时候算是"接受"——不仅仅是进入 Q3，还必须读到什么符号？

核心知识点

图灵机七元组 — M = (Q, Σ, Γ, δ, q₀, q_accept, q_reject)，每个元素的含义与本题对应
转移表驱动 vs 硬编码 — TRANSITION 二维数组查表，同一框架可加载不同转移表模拟不同 TM
纸带符号映射 — sym_to_idx() 将字符 'a'/'b'/'X'/'Y'/'_' 映射为 0~4 的查表索引
aⁿbⁿ 配对消去策略 — q0 标记 a→X, q1 找 b→Y, q2 回 X→q0, 循环直到全部配对
拒绝的多种场景 — 非法转移(δ 无定义)、n=0 空串、a 比 b 多、b 比 a 多、交错排列
停机问题 — 不存在通用算法判定任意 TM 是否停机，对角线法反证、Rice 定理
Church-Turing 论题 — 图灵可计算 = λ可计算 = 递归函数 = 直观可计算，所有计算模型等价

代码框架

66_turing_machine_sim.c

#include <stdio.h>
#include <string.h>

#define TAPE_SIZE 64
#define BLANK '_'

/* 读写头移动方向 */
#define LEFT  -1
#define RIGHT  1
#define HALT   0

/* 状态定义 */
#define Q0       0
#define Q1       1
#define Q2       2
#define Q3       3  /* 接受态 */
#define Q_REJECT 4

/* 转移表条目 */
typedef struct {
    int  next_state;
    char write_symbol;
    int  move;         /* LEFT, RIGHT, or HALT */
} Transition;

/* ─── 转移表（已提供，无需修改） ───
 * TRANSITION[state][symbol_index]
 *   symbol_index: 0='a', 1='b', 2='X', 3='Y', 4='_' (blank)
 *   next_state = -1 表示"此状态/符号组合无合法转移 → 拒绝"
 */
static const Transition TRANSITION[5][5] = {
    /* q0 */ {
        /* a */ {Q1, 'X', RIGHT},
        /* b */ {-1, 'b', HALT},
        /* X */ {-1, 'X', HALT},
        /* Y */ {Q3, 'Y', RIGHT},
        /* _ */ {-1, '_', HALT},
    },
    /* q1 */ {
        /* a */ {Q1, 'a', RIGHT},
        /* b */ {Q2, 'Y', LEFT},
        /* X */ {-1, 'X', HALT},
        /* Y */ {Q1, 'Y', RIGHT},
        /* _ */ {-1, '_', HALT},
    },
    /* q2 */ {
        /* a */ {Q2, 'a', LEFT},
        /* b */ {-1, 'b', HALT},
        /* X */ {Q0, 'X', RIGHT},
        /* Y */ {Q2, 'Y', LEFT},
        /* _ */ {-1, '_', HALT},
    },
    /* q3 */ {
        /* a */ {-1, 'a', HALT},
        /* b */ {-1, 'b', HALT},
        /* X */ {-1, 'X', HALT},
        /* Y */ {Q3, 'Y', RIGHT},
        /* _ */ {Q3, '_', HALT},
    },
    /* q_reject（所有转移均拒绝） */ {
        {-1, 'a', HALT}, {-1, 'b', HALT},
        {-1, 'X', HALT}, {-1, 'Y', HALT}, {-1, '_', HALT},
    },
};

static const char *STATE_NAMES[] = {"q0", "q1", "q2", "q3", "q_reject"};

/* 符号 → 查表索引（已提供） */
static int sym_to_idx(char c) {
    switch (c) {
        case 'a': return 0;
        case 'b': return 1;
        case 'X': return 2;
        case 'Y': return 3;
        case '_': return 4;
        default:  return 4;
    }
}

/* ─── TODO 1: init_tape ───
 * 用 BLANK 填充整条纸带，再将输入字符串复制到纸带上。
 * 读写头从位置 0 开始。 */
static void init_tape(char tape[], int tape_size, const char *input) {
    // ① for i = 0..tape_size-1: tape[i] = BLANK

    // ② 用 strlen 获取 input 长度

    // ③ for i = 0..len-1: tape[i] = input[i]
}

/* ─── TODO 2: print_tape ───
 * 打印纸带内容、读写头位置和当前状态。
 * 格式: "Tape: [a b c ...], head=N, state=qX\n"
 * 只打印到最右非 BLANK 符号 + 额外 2 个 BLANK。 */
static void print_tape(const char tape[], int tape_size, int head, int state) {
    // ① 找到最右非 BLANK 的位置 rightmost

    // ② 从 0 到 rightmost+2 打印，符号间用空格分隔
    //    注意 第一个符号前不要有空格

    // ③ printf(", head=%d, state=%s\n", head, STATE_NAMES[state])
}

/* ─── TODO 3: step ───
 * 执行一次图灵机转移：查表、写符号、移头、换状态。
 * 如果查到的 next_state == -1：直接返回 Q_REJECT。
 * 移头后 clamp 到 [0, tape_size-1] 防止越界。 */
static int step(char tape[], int tape_size, int *head, int state) {
    // ① si = sym_to_idx(tape[*head])       // 符号 → 查表索引

    // ② Transition t = TRANSITION[state][si] // 查表

    // ③ if t.next_state == -1: return Q_REJECT

    // ④ tape[*head] = t.write_symbol        // 写纸带

    // ⑤ *head += t.move                     // 移动读写头

    // ⑥ clamp head 到 [0, tape_size-1]

    // ⑦ return t.next_state
}

/* ─── TODO 4: run ───
 * 运行图灵机：初始化纸带 → 打印 → 循环步进直到接受/拒绝 */
static int run(const char *input) {
    // ① char tape[TAPE_SIZE]; int head = 0; int state = Q0
    //    init_tape(tape, TAPE_SIZE, input)

    // ② printf("Input: \"%s\"\n", input)
    //    print_tape(tape, TAPE_SIZE, head, state)

    // ③ 循环:
    //    a. if state == Q_REJECT: printf reject, return 0
    //    b. if state == Q3 && tape[head] == BLANK: printf accept, return 1
    //    c. state = step(tape, TAPE_SIZE, &head, state)
    //    d. print_tape(tape, TAPE_SIZE, head, state)
    //    e. if state == Q_REJECT: printf reject, return 0
    //    f. if state == Q3 && tape[head] == BLANK: printf accept, return 1
}

/* ─── TODO 5: main ─── */
int main(void) {
    // ① printf("=== Turing Machine Simulator for L = {a^n b^n | n >= 1} ===\n")
    // ② run("aaabbb")
    // ③ run("aab")
    // ④ return 0
}

骨架中转移表 TRANSITION[5][5] 和 sym_to_idx() 已完整提供。你需要在五个 TODO 位置填写实现代码。核心挑战是：step() 中如何用三行代码完成"查索引→查表→写/移/换"？run() 的循环终止条件是什么？为什么接受判定不仅要状态是 Q3，还要当前读到 BLANK？

TIP

先不要往下翻看参考解答。在纸上画一条纸带，用 "aabb" 手工追踪一遍——列出每一步的状态、纸带内容和读写头位置。理解了手工流程之后，代码自然会写出来。

深度讲解

1. 图灵机的形式化定义——七元组与转移函数

1.1 图灵机是什么

图灵机（Turing Machine, TM）是 Alan Turing 于 1936 年提出的抽象计算模型，用于精确定义""可计算"（computable）这一概念。它虽然结构简单——只有一条纸带、一个读写头、一个有限状态控制器——但能计算任何可计算的东西。

图灵机的物理结构:

    ┌──────────────────────────────────────────┐
    │         有限状态控制器 (Finite Control)     │
    │                                          │
    │  ┌──────────────────────────────┐        │
    │  │  当前状态: q0                 │        │
    │  │  转移规则表:                  │        │
    │  │    δ(q0,a) = (q1,X,R)       │        │
    │  │    δ(q1,b) = (q2,Y,L)       │        │
    │  │    δ(q2,X) = (q0,X,R)       │        │
    │  └──────────────────────────────┘        │
    │              │                            │
    │              │ 读写头 (Read/Write Head)    │
    │              ↓                            │
    └──────────────┬───────────────────────────┘
                   │
    ┌──┬──┬──┬──┬──┴──┬──┬──┬──┬──┬──┬──┬──┐
    │a │a │a │b │ b │b │_ │_ │_ │_ │_ │_ │...│
    ─┬──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
    ← 单向/双向无限纸带 (Infinite Tape) →

图灵机与有限自动机（DFA/NFA）和下推自动机（PDA）的本质区别：

特性	DFA/NFA	PDA	Turing Machine
存储方式	只读输入带	只读输入带 + 栈	无限可读写纸带
读写头移动	单向 (→)	单向 (→)	双向 (↔)
可写入纸带	否	否	是
识别的语言类	正则语言	上下文无关语言	递归可枚举语言
能否识别 aⁿbⁿ	❌	✅	✅
能否识别 a aⁿbⁿcⁿ	❌	❌	✅

1.2 七元组形式化定义

图灵机 M 是一个七元组：

M = (Q, Σ, Γ, δ, q₀, q_accept, q_reject)

Q        : 有限状态集         本题: {q0, q1, q2, q3, q_reject}
Σ        : 输入字母表         本题: {a, b}
Γ        : 纸带字母表         本题: {a, b, X, Y, _}  (Γ ⊇ Σ, _ ∈ Γ\Σ)
δ        : 转移函数            本题: TRANSITION 二维表
q₀       : 初始状态           本题: q0
q_accept : 接受状态           本题: q3
q_reject : 拒绝状态           本题: q_reject

转移函数 δ 的签名：

δ: Q × Γ → Q × Γ × {L, R, H}

对于当前状态 q 和纸带当前位置符号 s：
  δ(q, s) = (q', s', d)

  q' : 下一状态
  s' : 写入纸带的符号（覆盖当前位置）
  d  : 读写头移动方向（L=左移, R=右移, H=停机）

IMPORTANT

转移函数 δ 的确定性：对于每个 (q, s) 组合，最多只有一条转移规则。如果某个 (q, s) 没有定义转移规则，图灵机拒绝该输入。本题中用 next_state = -1 表示"无转移"，step() 检测到后直接返回 Q_REJECT。

1.3 纸带字母表为什么比输入字母表大

Γ \ Σ = {X, Y, _}   ← 这些符号不在输入中出现，而是 TM 运行时"写"出来的

X : 标记已消去的 a （"已处理的 a"）
Y : 标记已消去的 b （"已配对的 b"）
_ : 空白（纸带的默认填充符号，表示"此处无内容"）

图灵机能改写纸带——这一点使它比 FA 和 PDA 更强。用标记符号（X, Y）代替擦除避免了信息丢失，同时提供了"这个位置已经处理过了"的信号给后续步骤。

2. 纸带与状态的结构化表示——从理论到 C 代码

2.1 纸带数组

图灵机的无限纸带在实现中截断为有限数组 char tape[TAPE_SIZE]。对于本题的测试输入（最长的 aaabbb 仅 6 个字符），TAPE_SIZE=64 足够使用。

索引: 0   1   2   3   4   5   6   7  ... 63
内容: a | a | a | b | b | b | _ | _ | ... _ |
      ↑ head=0

tape_init_concept.c

/* init_tape 的正确顺序：先全填 BLANK，再覆盖输入 */
static void init_tape(char tape[], int tape_size, const char *input) {
    for (int i = 0; i < tape_size; i++)
        tape[i] = BLANK;        // ① 先全部填 BLANK

    int len = strlen(input);
    for (int i = 0; i < len && i < tape_size; i++)
        tape[i] = input[i];      // ② 再覆盖输入字符
    // head 始终从 0 开始（在 run() 中初始化）
}

WARNING

必须先填 BLANK 再复制输入。如果反过来——先复制输入再填 BLANK——会把输入覆盖掉。另外，用 sizeof(tape) 获取纸带大小在函数参数中无效（退化为指针大小），必须传入 tape_size。

2.2 符号映射表——从字符到数组索引

转移表 TRANSITION[5][5] 用整数索引而非字符下标。sym_to_idx() 完成字符到索引的映射：

sym_to_idx.c

/* 纸带符号 → 查表索引的映射规则 */
int sym_to_idx(char c) {
    switch (c) {
        case 'a': return 0;  // 输入字符 a
        case 'b': return 1;  // 输入字符 b
        case 'X': return 2;  // 标记符号：已处理的 a
        case 'Y': return 3;  // 标记符号：已配对的 b
        case '_': return 4;  // 空白
        default:  return 4;  // 未知字符当空白处理
    }
}

2.3 状态枚举——整数 vs 字符串

状态在内部用整数（#define Q0 0, Q1 1, etc.），在打印时用字符串数组转换：

state_names.c

static const char *STATE_NAMES[] = {"q0", "q1", "q2", "q3", "q_reject"};

// 打印当前状态: printf("%s", STATE_NAMES[state]);

NOTE

整数状态值可以直接作为转移表的第一维下标 TRANSITION[state][si]，无需额外映射。这是用整数而不是字符串表示状态的工程原因。

3. aⁿbⁿ 识别状态机——配对消去策略

3.1 问题本质：为什么 aⁿbⁿ 不是正则语言

语言 L = {aⁿbⁿ | n ≥ 1} 要求 a 和 b 的数量相等。正则语言（能被 DFA/NFA 识别的语言）没有"计数"能力——DFA 只有有限的状态，无法记住"读了多少个 a"。用泵引理（Pumping Lemma）可以严格证明 aⁿbⁿ 不是正则语言。

下推自动机（PDA）通过一个栈可以"记住" a 的个数（每读一个 a 压栈，每读一个 b 弹栈），因此能识别 aⁿbⁿ。但 PDA 能识别的 aⁿbⁿcⁿ 需要两个计数器（a 和 b 的数量都要记住），栈只有"后进先出"一个维度，所以 PDA 也不行。只有图灵机可以。

3.2 配对消去法的状态转移图

本题图灵机使用经典的"配对消去法"：

标记最左的 a 为 X，向右找第一个 b
标记那个 b 为 Y，向左回到 X 的位置
右移一格找下一个 a，重复
全部 a 变成 X 且全部 b 变成 Y → 接受

状态转移图:

               a/X,R
         ┌──────────────┐
         │              │
    ┌────▼───┐    a/a,R │   ┌──────────┐
    │   q0   ├──────────┼──►│    q1    │
    │  (初始) │          │   │ (向右右扫描)│
    └──┬──┬──┘          │   └────┬─────┘
       │  │             │        │
 Y/Y,R │  │ X/X,R       │   b/Y,L│
       │  │      ┌──────┘        │
       │  │      │               │
    ┌──▼──┴──┐   │    ┌────────────▼──┐
    │   q3   │   │    │     q2      │
    │ (接受态) │   │    │  (向左回扫)  │
    └──┬─────┘   │    └──────┬──────┘
                  │           │
  Y/Y,R│         │      a/a,L│ Y/Y,L
       │         │           │
   ┌───▼──┐      │           │
   │ ACCEPT│     │           │
   └──────┘      └───────────┘

3.3 转移函数逐条解析

δ(q0, a) = (q1, X, R)   ← 标记最左的 a 为 X，切换到搜索 b 模式
δ(q0, Y) = (q3, Y, R)   ← 所有 a 已匹配完，进入验收阶段
δ(q0, _) = 无定义 → 拒绝  ← 输入为空串 (n=0)
δ(q0, b) = 无定义 → 拒绝  ← 输入以 b 开头，违反 aⁿbⁿ 格式

δ(q1, a) = (q1, a, R)   ← 向右跳过未标记的 a
δ(q1, Y) = (q1, Y, R)   ← 向右跳过已匹配的 Y
δ(q1, b) = (q2, Y, L)   ← 找到最左的 b！标记为 Y，切换为回扫模式
δ(q1, _) = 无定义 → 拒绝  ← 找不到对应的 b（a 比 b 多）

δ(q2, a) = (q2, a, L)   ← 向左跳过 a
δ(q2, Y) = (q2, Y, L)   ← 向左跳匹配的 Y
δ(q2, X) = (q0, X, R)   ← 找到本轮标记的 X，准备下一轮
δ(q2, b) = 无定义 → 拒绝  ← 不应在 q2 遇到未标记的 b

δ(q3, Y) = (q3, Y, R)   ← 验收：向右扫描所有 Y，确认全是 Y
δ(q3, _) = 停机 → 接受   ← 读到空白，且全是 Y → 接受！
δ(q3, a) = 无定义 → 拒绝  ← 有多余的 a
δ(q3, b) = 无定义 → 拒绝  ← 有多余的 b

NOTE

注意 δ(q3, _) 的特殊处理：next_state 仍然是 Q3（不会变成新状态），但 move = HALT 表示停机。在 run() 循环中，当 state == Q3 && tape[head] == BLANK 时判定接受——这正对应了"进入接受态且读到空白后停机"。

4. 转移表的查表实现——数据驱动的编程思想

4.1 TRANSITION 二维数组的结构

转移表是一个 Transition[5][5] 的二维数组：

TRANSITION[state][symbol_index] = { next_state, write, move }

          symbol_index →
          a(0)  b(1)  X(2)  Y(3)  _(4)
state  ┌──────┬──────┬──────┬──────┬──────┐
↓ q0   │ q1,X │ 拒绝  │ 拒绝  │ q3,Y │ 拒绝  │
  q1   │ q1,a │ q2,Y │ 拒绝  │ q1,Y │ 拒绝  │
  q2   │ q2,a │ 拒绝  │ q0,X │ q2,Y │ 拒绝  │
  q3   │ 拒绝  │ 拒绝  │ 拒绝  │ q3,Y │ 接受  │
  q_rej│ 拒绝  │ 拒绝  │ 拒绝  │ 拒绝  │ 拒绝  │
       └──────┴──────┴──────┴──────┴──────┘

4.2 step() 的查表流程

step_lookup.c

static int step(char tape[], int tape_size, int *head, int state) {
    // 步骤 1: 读当前位置的符号，映射为查表索引
    int si = sym_to_idx(tape[*head]);

    // 步骤 2: 查转移表——O(1) 直接索引
    Transition t = TRANSITION[state][si];

    // 步骤 3: 检查是否有合法转移
    if (t.next_state == -1)
        return Q_REJECT;

    // 步骤 4: 执行转移——写、移、换
    tape[*head] = t.write_symbol;          // 写入新符号
    *head += t.move;                       // 移动读写头

    // 步骤 5: 边界安全——clamp 头位置
    if (*head < 0) *head = 0;
    if (*head >= tape_size) *head = tape_size - 1;

    return t.next_state;                   // 返回新状态
}

步骤	操作	代码	复杂度
1	字符 → 索引	`sym_to_idx(tape[*head])`	O(1)
2	查转移表	`TRANSITION[state][si]`	O(1)
3	检查合法性	`if (t.next_state == -1)`	O(1)
4	执行转移	`tape[head] = ...; head += ...`	O(1)

IMPORTANT

为什么要用查表而不是 if/else？查表法是"数据驱动编程"的体现——同样的 step() 代码可以加载不同的转移表来模拟不同的图灵机。只要 TRansition 表内容不同，模拟的就是不同的图灵机程序。这是通用图灵机的思想基础。

4.3 读写头越界保护

图灵机的纸带理论上无限长，但实现中纸带大小有限。当读写头试图超出范围时需要 clamp：

head_clamp.c

/* 读写头 clamp —— 防止数组越界 */
*head += t.move;
if (*head < 0) *head = 0;                   // 左边界
if (*head >= tape_size) *head = tape_size - 1; // 右边界

对于本题 TAPE_SIZE=64 和测试输入（最长 6 字符），正常运行时不会触发越界。但这是一个良好的防御性编程实践——万一转移表有 bug 导致读写头跑出范围，也不会出现未定义行为。

5. 完整纸带追踪——手把手走查算法

5.1 接受案例: "aaabbb" 的 24 步追踪

输入 "aaabbb" → 三轮配对消去 → ACCEPT ✓

══════════════════════════════════════════════════════
第 1 轮: 消去第 1 对 (a,b)
══╔════════════════════════════════════════════════════
 0   [a a a b b b _ _]  head=0  q0    (初始)
 1   [X a a b b b _ _]  head=1  q1    (q0 读 a→写 X, 右移, 转 q1)
 2   [X a a b b b _ _]  head=2  q1    (q1 读 a→不变, 右移, 保持 q1)
 3   [X a a b b b _ _]  head=3  q1    (q1 读 a→不变, 右移, 保持 q1)
 4   [X a a Y b b _ _]  head=2  q2    (q1 读 b→写 Y, 左移, 转 q2)
 5   [X a a Y b b _ _]  head=1  q2    (q2 读 a→不变, 左移, 保持 q2)
 6   [X a a Y b b _ _]  head=0  q2    (q2 读 a→不变, 左移, 保持 q2)
 7   [X a a Y b b _ _]  head=1  q0    (q2 读 X→不变, 右移, 转 q0)

══════════════════════════════════════════════════════
第 2 轮: 消去第 2 对 (a,b)
══════════════════════════════════════════════════════
 8   [X X a Y b b _ _]  head=2  q1    (q0 读 a→写 X, 右移, 转 q1)
 9   [X X a Y b b _ _]  head=3  q1    (q1 读 a→不变, 右移, 保持 q1)
10   [X X a Y b b _ _]  head=4  q1    (q1 读 Y→不变, 右移, 保持 q1)
11   [X X a Y Y b _ _]  head=3  q2    (q1 读 b→写 Y, 左移, 转 q2)
12   [X X a Y Y b _ _]  head=2  q2    (q2 读 Y→不变, 左移, 保持 q2)
13   [X X a Y Y b _ _]  head=1  q2    (q2 读 a→不变, 左移, 保持 q2)
14   [X X a Y Y b _ _]  head=2  q0    (q2 读 X→不变, 右移, 转 q0)

══════════════════════════════════════════════════════
第 3 轮: 消去第 3 对 (a,b)
══════════════════════════════════════════════════════
15   [X X X Y Y b _ _]  head=3  q1    (q0 读 a→写 X, 右移, 转 q1)
16   [X X X Y Y b _ _]  head=4  q1    (q1 读 Y→不变, 右移, 保持 q1)
17   [X X X Y Y b _ _]  head=5  q1    (q1 读 Y→不变, 右移, 保持 q1)
18   [X X X Y Y Y _ _]  head=4  q2    (q1 读 b→写 Y, 左移, 转 q2)
19   [X X X Y Y Y _ _]  head=3  q2    (q2 读 Y→不变, 左移, 保持 q2)
20   [X X X Y Y Y _ _]  head=2  q2    (q2 读 Y→不变, 左移, 保持 q2)
21   [X X X Y Y Y _ _]  head=3  q0    (q2 读 X→不变, 右移, 转 q0)

══════════════════════════════════════════════════════
验收阶段: q0 读 Y → 转 q3, 向右扫过所有 Y → ACCEPT
══════════════════════════════════════════════════════
22   [X X X Y Y Y _ _]  head=4  q3    (q0 读 Y→转 q3, 右移)
23   [X X X Y Y Y _ _]  head=5  q3    (q3 读 Y→右移, 保持 q3)
24   [X X X Y Y Y _ _]  head=6  q3    (q3 读 Y→右移, 保持 q3)
     此时 head=6, tape[6]='_', state=Q3 → ACCEPT!

5.2 拒绝案例: "aab" 的 8 步追踪

输入 "aab" → a 比 b 多 → REJECT ✗

══════════════════════════════════════════════════════
第 1 轮: 消去第 1 对
══════════════════════════════════════════════════════
 0   [a a b _ _]    head=0  q0    (初始)
 1   [X a b _ _]    head=1  q1    (q0 读 a→X, R, q1)
 2   [X a b _ _]    head=2  q1    (q1 读 a→R, 保持 q1)
 3   [X a Y _ _]    head=1  q2    (q1 读 b→Y, L, q2)
 4   [X a Y _ _]    head=0  q2    (q2 读 a→L, 保持 q2)
 5   [X a Y _ _]    head=1  q0    (q2 读 X→R, q0)

══════════════════════════════════════════════════════
第 2 轮: 试图消去第 2 对 — 失败！
╔══════════════════════════════════════════════════════
 6   [X X Y _ _]    head=2  q1    (q0 读 a→X, R, q1)
 7   [X X Y _ _]    head=3  q1    (q1 读 Y→R, 保持 q1)
 8   [X X Y _ _]    head=3  q_reject (q1 读 _ → 无转移！REJECT)

拒绝原因: δ(q1, _) 无定义。q1 在寻找匹配的 b 时，读到了空白——
说明 a 比 b 多，输入不合法。

6. 停机问题——计算理论的"天花板"

6.1 什么是停机问题

停机问题（Halting Problem）是计算机科学中最著名的不可判定问题——不存在一个通用算法可以判定任意程序在任意输入上是否会停机。

停机问题 (Halting Problem):

  输入: 一个程序 P (或图灵机 M) 和一个输入 w
  输出: Yes (P(w) 会停机) 或 No (P(w) 会死循环)
  
  结论: 不存在算法能对所有 (P, w) 给出正确答案。

6.2 证明概要（图灵的对角线法）

假设存在算法 H(P, w) 能判定停机。

构造"悖论机" D:
  D(x):
    if H(x, x) == "会停机":
      while (1) {}   // 故意死循环
    else:
      halt           // 立即停机

现在问: D(D) 是否会停机?

  情况 A: D(D) 停机
    → 进入 if 分支 → H(D, D) == "会停机"
    → 执行死循环 → D(D) 不停机 → 矛盾！

  情况 B: D(D) 不停机
    → 跳过 if 分支 → H(D, D) != "会停机"
    → 执行 halt → D(D) 停机 → 矛盾！

因此 H 不可能存在。 ∎

6.3 停机问题的实际含义

停机问题的推论（Rice 定理的特例）:

  ❌ 无法写出能检测所有死循环的调试器
  ❌ 无法写出能证明任意程序正确性的验证器  
  ❌ 无法写出能判断两个程序是否完全等价的工具
  ❌ 无法写出能检测所有缓冲区溢出的静态分析器

这些不是"暂时没找到算法"，而是"在数学上被证明不存在算法"。

实践中，我们只能做"足够好"的近似——
  启发式检测、有限状态抽象、特定语言的约束分析。

NOTE

停机问题的不可判定性并不意味着我们写不出有用的程序分析工具。像 Valgrind、AddressSanitizer、Coverity 等工具在实践中非常有效——它们检查"特定类别的 bug"，而不是试图解决通用的停机问题。关键在于将"不可判定问题"转换为"可判定的近似问题"。

7. Church-Turing 论题与图灵完备性

7.1 Church-Turing 论题

┌─────────────────────────────────────────────────────┐
│               Church-Turing 论题                     │
│                                                     │
│  "任何直观上可计算的函数都可以被图灵机计算。"          │
│                                                     │
│  等价表规则表:                                           │
│  - 图灵可计算 = λ可计算 = 递归函数 = 直观可计算       │
│  - 不存在比图灵机更强的"合理"计算模型                  │
│                                                     │
│  注意: 这不是数学定理，而是经验假说。                  │
│  因为"直观可计算"不是形式化的精确定义。                │
│                                                     │
│  但从 1936 年至今，所有认真提出的计算模型都不比       │
│  图灵机更强——这为论题提供了强有力的经验支持。          │
└──────────────────────────────────────────────────────┘

7.2 图灵完备性

一个系统被称为图灵完备（Turing-complete）的，当且仅当它能模拟通用图灵机。

图灵完备的	不是图灵完备的
C, Python, Java...	正则表达式
C++ 模板元编程	CSS
Excel 公式	SQL（纯查询，无递归）
Minecraft 红石	HTML
Conway 生命游戏	JSON
x86 汇编	YACC grammar

TIP

图灵完备性是编程语言的一个重要分界线：图灵完备意味着语言能解决"任何可计算问题"。但图灵完备并不保证效率——有些图灵完备系统（如 C++ 模板）理论上能算任何东西，但编译时间可能极其漫长。

7.3 通用图灵机——"存储程序"的思想来源

通用图灵机（Universal Turing Machine, UTM）能读取另一台图灵机的描述（转移表）并在纸带上模拟它。这直接启发了冯·诺依曼架构的核心思想：

通用图灵机 = 冯·诺依曼架构的抽象模型

  通用图灵机:          冯·诺依曼架构:
  ┌──────────────┐    ┌──────────────┐
  │ 转移表(程序)    │    │ 内存中的机器码  │
  │ 纸带(数据)     │    │ 内存中的数据    │
  │ 有限控制器     │    │ CPU           │
  └──────────────┘    └──────────────┘

  核心: 程序也是数据，可以存储在"纸带"/"内存"中。

这条思想线索——从图灵 1936 年的理论论文，到冯·诺依曼 1945 年的 EDVAC 报告，再到你手中的任何一台计算机——是计算机科学最优雅的知识传承之一。

参考解答

练习1: init_tape — 纸带初始化

solution_66_turing_machine_init_tape.c

static void init_tape(char tape[], int tape_size, const char *input) {
    /* 先全部填 BLANK */
    for (int i = 0; i < tape_size; i++)
        tape[i] = BLANK;

    /* 再复制输入字符串 */
    int len = strlen(input);
    for (int i = 0; i < len && i < tape_size; i++)
        tape[i] = input[i];

    /* 读写头从 0 开始（由 run() 中的 head=0 负责） */
}

要点：必须先填 BLANK 再复制输入，否则输入会被 BLANK 覆盖。用 strlen(input) 获取长度，用 i < tape_size 防止越界。

练习2: print_tape — 纸带打印

solution_66_turing_machine_print_tape.c

static void print_tape(const char tape[], int tape_size, int head, int state) {
    /* 找到最右非 BLANK 的位置 */
    int rightmost = -1;
    for (int i = 0; i < tape_size; i++) {
        if (tape[i] != BLANK)
            rightmost = i;
    }
    if (rightmost < 0) rightmost = 0;

    /* 打印纸带符号（第一个符号前不加空格） */
    printf("Tape: [");
    int end = rightmost + 2;
    if (end >= tape_size) end = tape_size - 1;
    for (int i = 0; i <= end; i++) {
        if (i > 0) printf(" ");
        printf("%c", tape[i]);
    }

    /* 打印头位置和状态 */
    printf("], head=%d, state=%s\n", head, STATE_NAMES[state]);
}

要点：找到最右非 BLANK 后额外打印 2 个 BLANK；第一个符号前不加空格，后续符号前加空格；用 STATE_NAMES[state] 转换状态名。

练习3: step — 核心转移函数

solution_66_turing_machine_step.c

static int step(char tape[], int tape_size, int *head, int state) {
    /* 1. 符号 → 查表索引 */
    int si = sym_to_idx(tape[*head]);

    /* 2. 查转移表 */
    Transition t = TRANSITION[state][si];

    /* 3. 无合法转定义 → 拒绝 */
    if (t.next_state == -1)
        return Q_REJECT;

    /* 4. 执行转移：写符号 → 移读写头 */
    tape[*head] = t.write_symbol;
    *head += t.move;

    /* 5. Clamp 读写头到合法范围 */
    if (*head < 0) *head = 0;
    if (*head >= tape_size) *head = tape_size - 1;

    return t.next_state;
}

要点：整个函数的逻辑就是"读→查→判→写→移→返回"。注意 t.next_state == -1 的判断必须在访问 t.write_symbol 和 t.move 之后发生——因为转移表条目的这三个字段始终是有效的，只有 next_state == -1 表示"此转移不可用"。

课堂讨论

图灵机的纸带理论上无限长，为什么本题中 TAPE_SIZE=64 就够用了？实际编程中如何确定合适的纸带大小？
δ(q3, _) = (q3, _, HALT) 为什么 next_state 还是 Q3 而不是一个新的"接受状态"？如果在 step() 中直接检测到 HALT 就返回接受，会有什么问题？
如果把 aⁿbⁿ 识别问题改为 aⁿbⁿcⁿ（a, b, c 数量相等），需要怎样修改状态机和转移表？额外需要几个状态？

讨论答案

Q1: 纸带大小为什么 64 就够了？

图灵机的无限纸带是理论模型——目的是让纸带永远不会不够用。在实际编程中，纸带大小由输入规模决定。

本题测试输入 "aaabbb" 仅 6 个字符，算法运行过程中 TM 的读写头移动范围不超过 输入长度 + 2（因为只向右搜索 b，向左回到 X 再右移一格）。加上 2 个额外的 BLANK 用于打印展示，总需求 < 10。

选择 TAPE_SIZE=64 是"足够大"的安全余量，远大于实际需求。在工程实践中，确定纸带大小的策略是：

分析算法读写头的最大位移量
加上合理的 buffer（如 2 倍）
对于不可预知的情况（如循环移动的 TM），需要动态扩展纸带（realloc）

本题中 aⁿbⁿ 策略是来回消去——最右只到末尾的 b，不会无限向右扩展，因此静态固定大小完全够用。

Q2: q3 读到 BLANK 时为何保持 Q3 并 HALT？

δ(q3, _) = (q3, _, HALT) 的 next_state 保持 Q3 是一个约定：接受和拒绝不是转移表决定的，而是由 run() 的循环判定逻辑决定的。

在 step() 函数层面，HALT 就是"本次不移动读写头"。step() 返回 Q3（而不是某个特殊值），然后 run() 循环中的判据检查 state == Q3 && tape[head] == BLANK 来判定接受。

如果直接让 step() 检测到 HALT 就返回一个特殊的"ACCEPT"值，会有两个问题：

需要引入额外的状态码，与状态枚举体系混在一起
HALT 不一定意味着"接受"——图灵机停在拒绝态也属于停机。用外层的 run() 循环统一判断，逻辑更清晰。

halt_vs_accept.c

/* run() 中的正确判断逻辑 */
int new_state = step(tape, tape_size, &head, state);

// 先检查是否拒绝
if (new_state == Q_REJECT) { ... }

// 再检查是否接受：状态是 Q3 且读到 BLANK
if (new_state == Q3 && tape[head] == BLANK) { ... }

Q3: 如何扩展为 aⁿbⁿcⁿ？

aⁿbⁿcⁿ 需要配对消去三组符号，策略变为：

标记最左的 a 为 X，向右找第一个 b
标记该 b 为 Y，继续向右找第一个 c
标记该 c 为 Z，向左扫描回到 X
重复

额外需要的状态：

原版 aⁿbⁿ:   q0, q1, q2, q3, q_reject        (5 个状态)
aⁿbⁿcⁿ 版:  需要额外增加:
  q4: 向右找 c 的状态: q1 找 b 的镜像）
  q5: 向左扫描经过 c 和 Z 回到 Y

总共约 7-8 个状态。转移表规模从 5×5 扩展到 8×6。

anbncn_transition_sketch.c

/* aⁿbⁿcⁿ 转移表的核心新增行 */

/* q4 (找 c): 从 q1 标记 b→Y 后进入 */
// q4: (c, Z, L) → q5  (找到最左的 c，标记为 Z，向左返回)
// q4: (b, b, R) → q4  (跳过更多 b)
// q4: (Z, Z, R) → q4  (跳过已标记的 Z)

/* q5 (回扫): 从 q4 标记 c→Z 后进入，向左找 Y */
// q5: (b, b, L) → q5  (跳回 b)
// q5: (Z, Z, L) → q5  (跳过 Z)
// q5: (Y, Y, R) → q2  (找到 Y，类比 aⁿbⁿ 中 q2 遇到 X)

这个扩展展示了转移表驱动设计的优势——增加状态只需添加 TRANSITION 表的行，step() 和 run() 的代码无需改变。

课后练习

实现 bⁿaⁿ 识别。修改转移表，使图灵机识别语言 L = {bⁿaⁿ | n ≥ 1}（b 在前，a 在后）。你只需要修改 TRANSITION 表，step() 和 run() 完全不用动。
知识点提示：交换 a 和 b 的角色——q0 标记最左的 b 为 X，q1 找 a。注意 q0 中原本对 b 的拒绝规则现在要改为标记转移。
添加步数统计。修改 run() 函数，在返回前打印 "Total steps: N\n"，其中 N 是从初始状态到接受/拒绝的总转移步数。对于 "aaabbb" 应该是 24，对于 "aab" 应该是 8。
知识点提示：在 run() 的循环开始前声明 int steps = 0;，每次调用 step() 后 steps++。注意步数统计的时机——在判定接受/拒绝之后递增。

通用图灵机的转移表加载。将 TRANSITION 表从 static const 改为通过函数参数传入 run()，实现 int run_with_table(const char *input, const Transition table[5][5])。然后用同一个框架加载 aⁿbⁿ 和 bⁿaⁿ 两张不同的转移表。

知识点提示：将 TRANSITION 的声明从文件级移动到 run() 的参数列表中。这就是"数据驱动"的直接体现——同样的循环逻辑，不同的数据，模拟不同的图灵机。step() 也需要接收转移表参数。

参考解答：bⁿaⁿ 转移表

ex1_bnan_transition.c

/* bⁿaⁿ 识别：交换 a 和 b 的角色，关键修改行用注释标出 */
static const Transition BnAn_TRANSITION[5][5] = {
    /* q0 */ {
        /* a */ {-1, 'a', HALT},  /* q0 遇到 a → 拒绝（格式错） */
        /* b */ {Q1, 'X', RIGHT}, /* 改: 标记最左的 b 为 X */
        /* X */ {-1, 'X', HALT},
        /* Y */ {Q3, 'Y', RIGHT}, /* 所有 b 已匹配，验收 */
        /* _ */ {-1, '_', HALT},
    },
    /* q1 */ {
        /* a */ {Q2, 'Y', LEFT},  /* 改: 找到 a，标记为 Y，回扫 */
        /* b */ {Q1, 'b', RIGHT}, /* 改: 跳过更多 b */
        /* X */ {-1, 'X', HALT},
        /* Y */ {Q1, 'Y', RIGHT}, /* 跳过已匹配的 Y */
        /* _ */ {-1, '_', HALT},
    },
    /* q2 */ {
        /* a */ {Q2, 'a', LEFT},  /* 跳过 a */
        /* b */ {Q2, 'b', LEFT},  /* 改: 跳过 b（回扫方向） */
        /* X */ {Q0, 'X', RIGHT}, /* 找到 X，下一轮 */
        /* Y */ {Q2, 'Y', LEFT},  /* 跳过 Y */
        /* _ */ {-1, '_', HALT},
    },
    /* q3, q_reject 与原表相同 */
};

要点：只需改三处——(1) q0 对 b 的转移从拒绝改为标记 X，(2) q1 找目标改为读 a 时标记 Y，(3) q2 回扫时增加跳过 b 的转移。step() 和 run() 完全不变。

参考解答：步数统计

ex2_step_count.c

static int run(const char *input) {
    char tape[TAPE_SIZE];
    int head = 0;
    int state = Q0;
    int steps = 0;  /* 新增：步数计数器 */

    init_tape(tape, TAPE_SIZE, input);
    printf("Input: \"%s\"\n", input);
    print_tape(tape, TAPE_SIZE, head, state);

    while (1) {
        /* 先检查终止条件 */
        if (state == Q_REJECT) {
            printf("Result: REJECT\n");
            printf("Total steps: %d\n", steps);  /* 新增 */
            return 0;
        }
        if (state == Q3 && tape[head] == BLANK) {
            printf("Result: ACCEPT\n");
            printf("Total steps: %d\n", steps);  /* 新增 */
            return 1;
        }

        state = step(tape, TAPE_SIZE, &head, state);
        steps++;  /* 新增：每步递增 */

        print_tape(tape, TAPE_SIZE, head, state);
    }
}

要点：步数 steps 初始化为 0，在每次 step() 调用后递增。注意不要在 step() 内部递增——step() 只负责单个转移，不知道后续还会不会继续。

参考解答：通用转移表加载

ex3_universal_tm.c

/* step() 接收转移表参数 */
static int step_with_table(char tape[], int tape_size, int *head,
                           int state,
                           const Transition table[5][5]) {
    int si = sym_to_idx(tape[*head]);
    Transition t = table[state][si];

    if (t.next_state == -1) return Q_REJECT;

    tape[*head] = t.write_symbol;
    *head += t.move;
    if (*head < 0) *head = 0;
    if (*head >= tape_size) *head = tape_size - 1;
    return t.next_state;
}

/* run() 接收转移表参数 */
static int run_with_table(const char *input,
                           const Transition table[5][5]) {
    char tape[TAPE_SIZE];
    int head = 0, state = Q0;

    init_tape(tape, TAPE_SIZE, input);
    printf("Input: \"%s\"\n", input);
    /* ... 循环体同原 run(), 但调用 step_with_table */

    return (state == Q3 && tape[head] == BLANK) ? 1 : 0;
}

int main(void) {
    printf("=== Universal TM Demo ===\n");
    run_with_table("aaabbb", TRANSITION);     /* aⁿbⁿ → ACCEPT */
    run_with_table("bbbaaa", BnAn_TRANSITION); /* bⁿaⁿ → ACCEPT */
    return 0;
}

要点：这就是通用图灵机的雏形——同一个模拟器循环，通过加载不同的转移表来模拟不同的图灵机。冯·诺依曼的"存储程序"思想可以追溯到这一设计。

参考资料

Turing, A. M. (1936). "On Computable Numbers, with an Application to the Entscheidungsproblem." Proceedings of the London Mathematical Society, 2(42), 230-265. — 图灵机概念的原始论文
Sipser, M. (2012). Introduction to the Theory of Computation (3rd ed.). Cengage Learning. — 第 3-5 章：图灵机、可判定性与可计算性
Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2006). Introduction to Automata Theory, Languages, and Computation (3rd ed.). Pearson. — 第 8 章
维基百科: Turing machine — 图灵机
维基百科: Church-Turing thesis — Church-Turing 论题

"We can only see a short distance ahead, but we can see plenty there that needs to be done." — Alan Turing

Lesson 66: 图灵机 aⁿbⁿ 模拟器 ​

练习任务 ​

核心知识点 ​

代码框架 ​

深度讲解 ​

1. 图灵机的形式化定义——七元组与转移函数 ​

1.1 图灵机是什么 ​

1.2 七元组形式化定义 ​

1.3 纸带字母表为什么比输入字母表大 ​

2. 纸带与状态的结构化表示——从理论到 C 代码 ​

2.1 纸带数组 ​

2.2 符号映射表——从字符到数组索引 ​

2.3 状态枚举——整数 vs 字符串 ​

3. aⁿbⁿ 识别状态机——配对消去策略 ​

3.1 问题本质：为什么 aⁿbⁿ 不是正则语言 ​

3.2 配对消去法的状态转移图 ​

3.3 转移函数逐条解析 ​

4. 转移表的查表实现——数据驱动的编程思想 ​

4.1 TRANSITION 二维数组的结构 ​

4.2 step() 的查表流程 ​

4.3 读写头越界保护 ​

5. 完整纸带追踪——手把手走查算法 ​

5.1 接受案例: "aaabbb" 的 24 步追踪 ​

5.2 拒绝案例: "aab" 的 8 步追踪 ​

6. 停机问题——计算理论的"天花板" ​

6.1 什么是停机问题 ​

6.2 证明概要（图灵的对角线法） ​

6.3 停机问题的实际含义 ​

7. Church-Turing 论题与图灵完备性 ​

7.1 Church-Turing 论题 ​

7.2 图灵完备性 ​

7.3 通用图灵机——"存储程序"的思想来源 ​

参考解答 ​

课堂讨论 ​

讨论答案 ​

课后练习 ​

参考资料 ​

Lesson 66: 图灵机 aⁿbⁿ 模拟器

练习任务

核心知识点

代码框架

深度讲解

1. 图灵机的形式化定义——七元组与转移函数

1.1 图灵机是什么

1.2 七元组形式化定义

1.3 纸带字母表为什么比输入字母表大

2. 纸带与状态的结构化表示——从理论到 C 代码

2.1 纸带数组

2.2 符号映射表——从字符到数组索引

2.3 状态枚举——整数 vs 字符串

3. aⁿbⁿ 识别状态机——配对消去策略

3.1 问题本质：为什么 aⁿbⁿ 不是正则语言

3.2 配对消去法的状态转移图

3.3 转移函数逐条解析

4. 转移表的查表实现——数据驱动的编程思想

4.1 TRANSITION 二维数组的结构

4.2 step() 的查表流程

4.3 读写头越界保护

5. 完整纸带追踪——手把手走查算法

5.1 接受案例: "aaabbb" 的 24 步追踪

5.2 拒绝案例: "aab" 的 8 步追踪

6. 停机问题——计算理论的"天花板"

6.1 什么是停机问题

6.2 证明概要（图灵的对角线法）

6.3 停机问题的实际含义

7. Church-Turing 论题与图灵完备性

7.1 Church-Turing 论题

7.2 图灵完备性

7.3 通用图灵机——"存储程序"的思想来源

参考解答

课堂讨论

讨论答案

课后练习

参考资料