图灵机¶

本章问题：机器允许反复访问和改写旧数据后，怎样描述一次计算，并证明它会给出正确结果？

学习顺序：

1. 读懂纸带、转移和配置，区分接受、拒绝与无限运行。
2. 用标记法构造数量配对机器，证明正确性和停机。
3. 用明确接口组合移位、复制与多带模拟。
4. 理解图灵机与无限制文法的双向模拟。
5. 指定数值编码，区分原始递归、有界搜索和无界搜索。

可以反复改写的纸带¶

• PDA只能操作栈顶。
• 图灵机TM则有可读写纸带，读写头每步左右移动，能够回来检查和修改旧内容。
• 本章使用双向无限纸带；
• 任意有限时刻只访问有限格。
• 输入字母表 \(\Sigma\) 不含空白符 \(\square\)；
• 带字母表 \(\Gamma\) 还包含空白和工作标记。

• 有限状态集含初态 \(q_0\)、接受态 \(q_{acc}\)、拒绝态 \(q_{rej}\)。

• 转移 \(\delta(q,a)=(p,b,R)\) 表示状态q读到a，写b，头右移一格并进入p；

• L表示左移。
• 接受、拒绝都是停机，但输出结论不同；
• 还有第三种行为是永远运行。
• 没有列出的转移在本章示例中都视为拒绝停机，具体题目若另作约定就按其约定。

配置写成 \(uqv\)：纸带可见内容为uv，状态为q，头指向v首格。例如 \(abq\square\) 的头在右端空白。若 \(\delta(q,\square)=(r,X,L)\)，一步后是 \(arbX\)：原空白改X，头来到b。省去带段以外仍有空白。

书写配置时，状态符号的位置就是头的位置，不能只改状态名而不移位置。

一次转移同时改变纸带字符、状态和读写头位置。

输入属于 \(L(M)\) 当且仅当机器M最终接受它。识别器必须接受所有成员，非成员可拒绝或永远运行；判定器还必须对每个输入停机。证明机器是判定器，除答案正确，还要证明每次循环确实推进并最终结束。

练习 1¶

从配置读出一步计算¶

状态符号写在当前头下字符的左边。例如 \(abq\square\) 表示 a、b 已在头左侧，头正在读空白：

第二步结束时纸带仍为 abX，头指向 X；拒绝是一个已经结束的计算。写规则时，\(q,p\) 是状态，\(a,b\) 是带符号，\(L,R\) 是移动方向；进入新状态后，下一步才根据新头下字符选择规则。

“模拟了很久还没接受”尚不能确定非成员；识别器没有统一等待上限。

一次完整机器构造¶

• 先构造判定 \(\{0^n1^n:n\ge0\}\) 的机器。
• 用X标记已匹配的0，用Y标记已匹配的1。
• 阶段A从左向右找第一个未标记0，把它改X；
• 阶段B继续向右找第一个未标记1，把它改Y；
• 阶段C回到输入左端，重新执行A。
• 若B走到空白仍未找到1，拒绝。
• A若越过X后先遇Y，就检查剩余全为Y，检查成功接受；
• 若遇未匹配1或其他符号，拒绝。

这里每轮恰好消去一个未标记0和一个未标记1，保持两者原有数量差；成功检查保证数量差为零且顺序合法。反向，任何 \(0^n1^n\) 都能完成n轮配对。

每轮扫描在有限输入范围内结束，未标记0数量严格减少，所以机器对全部输入停机。空串一开始就通过尾部检查。

复杂机器可用“扫描到某标记”“返回左端”等宏组织。

宏是一段有限转移规则的缩写，接口必须写清进入时头在哪里、带内容满足什么条件、退出时头停哪里以及失败怎么处理，否则拼接两段正确程序也可能出错。

配对机的控制流程¶

flowchart TD
    A["回到输入左端，越过已标记 X"] --> C{"下一符号？"}
    C -->|"未标记 0"| X["改为 X，向右找未标记 1"]
    X --> F{"找到了吗？"}
    F -->|"找到 1"| Y["改为 Y，向左返回"]
    Y --> A
    F -->|"到空白仍未找到"| R["拒绝停机"]
    C -->|"Y 或空白"| T["检查剩余内容仅有 Y"]
    C -->|"未匹配 1"| R
    T -->|"检查通过"| E["接受停机"]
    T -->|"发现 0 或 1"| R

找 1 的阶段可越过剩余 0 和已有 Y，取首个尚未标记的 1。返回阶段向左扫到输入前的空白，再向右一格重启；本例不写空白到输入内部，因此这个边界明确。

这里 001 的第二轮已把 0 标为 X 后才发现缺少 1，所以最后是 XXY；终止前的带内容不必保留原输入，判断依赖扫描过程。

每轮未标记 0 至少减少一个，且每趟扫描范围有限，从而对合法与非法排列都保证停机。

移位与复制¶

• 设带段为 #ab□，头停在#，要在#后插入空格得到 #□ab□。
• 先扫描到末尾空白，再从右向左搬：把b复制到右边空白，回到原b格；
• 把a复制到原b格，回到原a格；
• 把原a格写空白，最后回到#。
• 搬运前先用有限状态记住当前字符，移到相邻格写下。
• 原串为空时直接结束。

若从左向右直接覆盖，把a写到b的位置后，原b已经丢失。因此右移从右往左，左移从左往右；方向保证尚未搬的内容不被覆盖。若题目指定别的退出头位置，还需补上最后扫描。

• 复制w可先写分隔符@，形成 #w@□。
• 从左端找首个未标记字符，用状态记住它并把原格改成对应标记；
• 右移越过@和已复制区，在末尾写该字符；
• 返回#。
• 重复至@前全部标记，再清除标记。
• 对ab依次得到 #Ab@a、#AB@ab、#ab@ab，大写仅表示已处理标记。
• 每轮增加一个已处理原字符，故终止；
• 按原串从左往右复制，保证顺序。
• 空串得到 #@，同样合法。

右移时保存尚未搬的字符¶

把 #ab□ 右移一格，按如下顺序追踪：

有限控制一次只需记住一个字符，字母表有限即可实现；任意长输入由多轮搬运处理。复制的策略也相同：工作标记记录“已经处理”，有限状态记录当前字符，循环逐步完成无固定上限的任务。

多带和分支怎样模拟¶

• 多带TM一步能同时读写固定k条带。
• 单带可把各带有限使用区放在分隔符之间，每段中用带帽符号标记读写头。
• 模拟一步分四阶段：扫描全部段收集k个头下符号；
• 结合旧状态算出转移；
• 再扫描改写旧头下符号并产生新头标记；
• 最后统一把新标记转成下一轮旧标记。
• 段末不够时用移位宏插入空白。

k固定且字母表有限，k个读入符号的组合只有有限多种，有限控制足以暂存。新旧头标记要区分，否则右移产生的新帽格可能在同一趟被再次处理，错误地模拟多步。

每轮开始编码真实配置，每个阶段精确落实转移，因此模拟器保持同样接受与停机行为，只是可能慢很多。

非确定TM的分支也能由确定TM模拟。将所有配置按运行步数分层，先展开深度0，再深度1、2。每个配置只有有限后继，每层有限；若某支在t步接受，第t层必被找到。

先把一条分支运行到结束可能被无限分支卡住，因此必须广度优先或交错推进。对识别能力，这保留“存在接受分支”的意义，不保证相同运行时间。

练习 2¶

练习 3¶

公平搜索按深度展开¶

flowchart TD
    S["深度 0：初始配置"] --> A["深度 1：枚举全部一步后继"]
    A --> B["深度 2：枚举这些配置的全部后继"]
    B --> C["逐层继续，任何接受配置出现就接受"]
    A --> X["某分支可能永远运行"]
    X -.->|"每层只推进有限步"| C

第 \(t\) 层访问运行了 \(t\) 步的所有分支。每个配置的分支数有固定有限上界，因此每层有限；先完成一层再进入下一层不会永久卡在某个分支。

若有接受分支，其长度是某个有限 \(t\)，最终一定访问到。若无接受分支，搜索可持续进行，这符合识别器语义。

文法也能模拟计算¶

无限制文法允许规则 \(\alpha\to\beta\) 的左侧含多个符号，但必须非空且至少含一个非终结符；右侧可任意，包括空串。仍是在当前句型中找到连续的 \(\alpha\) 并替换为 \(\beta\)。

任意无限制文法都能由TM识别：从S出发广度优先枚举推导，看到目标串就接受。每层有限，任何有限推导最终都会出现；不属于语言时可能永远搜索。

• 反过来，TM可转为无限制文法。
• 关键是同时保存原输入和工作纸带：用一个非终结符 \(C_{o,b}\) 代表一格，o为原输入字符或空标签 \(\bot\)，b为当前工作字符；
• 机器改写时只改b。
• 状态符号放在头下格左边。
• 对右移规则 \(\delta(q,b)=(p,c,R)\)，加入 \(qC_{o,b}\to C_{o,c}p\)；
• 对左移规则，加入 \(C_{r,d}qC_{o,b}\to pC_{r,d}C_{o,c}\)，枚举有限的相邻标签与字符。

生成阶段用边界L、R和标记G、J：\(S\to LGR\)，对每个输入字符a加入 \(G\to C_{a,a}G\)，最后 \(G\to JC_{\bot,\square}\)。用 \(C_{a,a}J\to JC_{a,a}\) 把J左移，\(LJ\to Lq_0\) 激活机器。G已经消失，此后不能继续生成原输入。

右移跨过编码边界时用 \(pR\to pC_{\bot,\square}R\) 补格；最左格左移时，对相应转移加入 \(LqC_{o,b}\to LpC_{\bot,\square}C_{o,c}\)。

接受后用 \(q_{acc}\to K\) 触发清理，\(C_{o,b}K\to KC_{o,b}\) 将K左移到边界，\(LK\to O\) 开始输出。输出规则为 \(OC_{a,b}\to aO\)、\(OC_{\bot,b}\to O\)，最后 \(OR\to\varepsilon\)。拒绝态没有清理出口。标签、状态和带符号都有限，所有这些规则族展开后仍是有限文法。

• 这几个规则族为何足够？
• 模拟开始的句型编码初始配置；
• 每次改写对应机器一步，按步数归纳始终是真配置。
• 全终结串必须经过接受清理，且清理输出始终是保存的原输入，所以生成串确实被机器接受；
• 反向，对接受输入先生成其初始编码，再照有限接受计算改写和清理，必能生成。
• 只输出工作带会出错，例如机器把输入全擦掉再接受，工作带已无法还原被接受的输入。

练习 4¶

自然数怎样输入输出¶

机器处理符号串，计算数值函数前必须指定编码。用一元编码 \(n\mapsto1^n\) 时，0编码为空串，多参数可写为 \(1^a\#1^b\)。输出也按约定编码，并固定完成时头位置。

全函数对每个输入有值；部分函数只在部分输入有定义。本章约定计算部分函数时，定义域内停机输出该值，定义域外不停机。把未定义输入拒绝停机，不满足这一约定。

原始递归函数从零函数 \(Z(n)=0\)、后继 \(S(n)=n+1\)、投影 \(P_i^k(x_1,\ldots,x_k)=x_i\) 开始，用复合与原始递归构造。投影只取第i个参数，复合就是把若干已知函数的输出传给另一个函数。原始递归规定

\(\vec x\) 表示其他参数组成的向量，g给初值，h给已完成n轮后的更新。循环次数由输入n事先限定，子函数都停机，所以这类函数必为全函数。

加法A由 \(A(a,0)=a,A(a,n+1)=S(A(a,n))\) 得到；乘法由 \(M(a,0)=0,M(a,n+1)=A(M(a,n),a)\) 得到。前驱 \(pred(0)=0,pred(n+1)=n\) 给出截断减法 \(D(a,0)=a,D(a,n+1)=pred(D(a,n))\)，故 \(D(a,b)=\max(a-b,0)\)，也记 \(\operatorname{monus}(a,b)\)。

最大值可写 \(\max(a,b)=A(a,D(b,a))\)。若 \(b\ge a\)，补上差值得b；若 \(b<a\)，截断差为零，得到a。表达式只复合已知原始递归函数，故仍原始递归。这种证明既要核算数值，也要说明构造合法。

练习 5¶

练习 6¶

原始递归就是指定初值和更新¶

加法 \(A(2,n)\) 的展开为：

一般递推中的 \(h(\vec x,n,f(\vec x,n))\) 同时知道固定参数、当前轮号和上轮结果，定义下一轮值。\(P_i^k\) 的上标 \(k\) 是参数个数，下标 \(i\) 是选择第几项，满足 \(1\le i\le k\)。

每次调用的递推次数由输入确定，所以原始递归保证全定义。

截断减法以 0 为下界，例如 \(D(2,5)=0\)，\(D(5,2)=3\)。它在自然数中输出，普通减法则可能得到负数。组合函数时必须沿用相同的数值集合和编码。

谓词与搜索¶

谓词用1表示真、0表示假。定义 \(iszero(0)=1,iszero(n+1)=0\)，然后 \(le(a,b)=iszero(D(a,b))\) 判断 \(a\le b\)，\(eq(a,b)=le(a,b)le(b,a)\) 判断相等。

若p取0或1，按p分段的函数可写 \(pf+(1-p)g\)，选择f或g；自然数减法可用D表达，因此只要p、f、g原始递归，结果仍原始递归。

• 有界搜索只检查 \(0,\ldots,b\)，无解可返回 \(b+1\)；
• 对原始递归谓词，可递推保存第一次命中位置，所以仍原始递归。
• 无界最小化 \(\mu y[P(\vec x,y)=1]\) 则从0依次寻找最小命中y。
• 若每次测试都结束且存在解，搜索返回；
• 无解则一直运行。
• 对部分谓词，较早候选的测试若不停机，顺序搜索也会卡住，不能越过它宣称后面的答案最小。

加入允许未定义的最小化后得到部分递归函数，与TM可计算的部分数值函数等价。一个方向由TM逐项执行基函数、复合、有限递推和搜索。

另一个方向把有限计算过程编码成自然数，用有限检查判断编码是否为合法停机记录，再搜索首个合法记录并抽取输出；机器不停止时搜索也不返回。这给出编码证明的机制。

全可计算仍比原始递归广：把全部一元原始递归表达式有效列为 \(e_0,e_1,\ldots\)，每个都可求值且停机。函数 \(d(n)=e_n(n)+1\) 全可计算。若d也原始递归，必等于某个 \(e_k\)，代入k得到 \(d(k)=d(k)+1\)，矛盾。

“能写递归程序”和“属于原始递归函数类”因此有严格区别。

练习 7¶

记忆要点¶

对应习题集¶

《计算理论分章习题集.pdf》的本章题目在 PDF 第 153–197 页（阅读器页序）。按习题集学习路线与代表题先完成对应代表题，再挑本章未见题练习。