1 第 8 章教材习题：题意释义与通用解题方法
本节不是逐题完整解答。 它为每个教材编号习题提供经页面核验的题意释义（Problem）、主题标签（Topic），以及本章层面的通用解题方法导引。本公开仓库不分发教材原图、转移表、边权与长表达式，因此具体数值、状态名与表达式需结合教材对应原页数据自行推导。同一类题的“方法导引”会重复出现，它说明的是解题思路，而不是该题的具体答案。
本章共收录 21 个教材编号习题。
1.1 习题 8.1.1
Source: textbook PDF p.234
Problem（教材题意释义）
把 hello-world 类不可解问题归约到：停机、是否产生输出、两个程序输出是否相同等问题。
Topic
按教材定义构造 + 正确性证明
方法导引（通用，非本题具体答案）
先明确归约方向：要证明目标问题 B 不可判定，从已知不可判定问题 A 构造可计算映射 f，使 x∈A 当且仅当 f(x)∈B。 对 TM 语义性质，优先使用 A_TM/停机问题或 Rice 定理；构造的新机器在触发已知问题的“是”实例时表现出目标性质，否则表现出明显相反的性质。 若还要分类为 RE/非 RE，则分别讨论半判定器是否能通过交错模拟、枚举见证来接受正例，并结合补语言或已知非 RE 语言排除更强类别。
Common mistakes
- 跳过量词、边界条件或接受方式；
- 把“存在一种构造”误写成“任意构造都成立”；
- 图表题未先准确抄录源数据就直接计算。
1.2 习题 8.2.1
Source: textbook PDF p.241
Problem（教材题意释义）
列出图 8-9 图灵机在 00、000111、00111 上的完整 ID 序列。
Topic
图灵机
方法导引（通用，非本题具体答案）
把教材页中的状态、边、权值或产生式先完整抄成一个有限表，然后严格按本章算法逐步计算；不要凭图形直觉跳步。 本题的可复现做法是：①列出源对象；②执行相应算法（状态消除/可区分表/PDA 的 ID 推演/CFG 推导/PCP 搜索等）；③每一步记录新状态、集合或配置；④用接受条件或不变量核对最终结果。 由于公开版不直接复制教材图表，精确的状态名、边权和表项以所标 PDF 页为准；算法步骤在这里完整给出，学习时可逐行对照源页复算。
Common mistakes
- 跳过量词、边界条件或接受方式；
- 把“存在一种构造”误写成“任意构造都成立”；
- 图表题未先准确抄录源数据就直接计算。
1.3 习题 8.2.2
Source: textbook PDF p.241
Problem（教材题意释义）
设计 TM：#0=#1；a^n b^n c^n；偶长度回文 ww^R。
Topic
TM
方法导引（通用，非本题具体答案）
先给出高层算法，再说明如何落实为有限控制与带操作。典型套路是多次扫描并把已处理符号做标记；多带机可把输入、工作区和计数分别放在不同带上；NTM 只把“猜一个候选”作为分支，随后仍需确定地验证。 正确性用循环不变量说明每轮扫描后哪些位置已经匹配/计数，停机性用每轮至少永久标记一个符号或严格缩小未处理区间证明。 要证明模型等价，则给出编码模拟：把多个带/多个头/二维坐标编码到一条带上，每个原机一步由有限次扫描模拟。
Common mistakes
- 跳过量词、边界条件或接受方式；
- 把“存在一种构造”误写成“任意构造都成立”；
- 图表题未先准确抄录源数据就直接计算。
1.4 习题 8.2.3
Source: textbook PDF p.242
Problem（教材题意释义）
为二进制整数加 1 的 TM 写出转移/状态功能，并跟踪 $111 等输入。
Topic
TM
方法导引（通用，非本题具体答案）
先给出高层算法，再说明如何落实为有限控制与带操作。典型套路是多次扫描并把已处理符号做标记；多带机可把输入、工作区和计数分别放在不同带上；NTM 只把“猜一个候选”作为分支，随后仍需确定地验证。 正确性用循环不变量说明每轮扫描后哪些位置已经匹配/计数，停机性用每轮至少永久标记一个符号或严格缩小未处理区间证明。 要证明模型等价，则给出编码模拟：把多个带/多个头/二维坐标编码到一条带上，每个原机一步由有限次扫描模拟。
Common mistakes
- 跳过量词、边界条件或接受方式；
- 把“存在一种构造”误写成“任意构造都成立”；
- 图表题未先准确抄录源数据就直接计算。
1.5 习题 8.2.4
Source: textbook PDF p.242
Problem（教材题意释义）
证明“函数计算机”和“函数图语言识别器”之间可以相互构造，并讨论部分函数。
Topic
按教材定义构造 + 正确性证明
方法导引（通用，非本题具体答案）
按题目定义直接建立形式化对象，并使用本章相应的标准构造或归纳证明。先写清楚输入、目标和不变量，再逐步给出构造；证明正确性时分别证明“构造出的对象不会接受/生成错误实例”和“每个合法实例都能被接受/生成”。 若题目是算法题，还要说明停机性与渐近复杂度；若是反例题，优先寻找最短、结构最简单的反例。
Common mistakes
- 跳过量词、边界条件或接受方式；
- 把“存在一种构造”误写成“任意构造都成立”；
- 图表题未先准确抄录源数据就直接计算。
1.6 习题 8.2.5
Source: textbook PDF p.242
Problem（教材题意释义）
根据教材给出的三组 TM 转移规则，逐个用不变量描述其语言。
Topic
TM
方法导引（通用，非本题具体答案）
把教材页中的状态、边、权值或产生式先完整抄成一个有限表，然后严格按本章算法逐步计算；不要凭图形直觉跳步。 本题的可复现做法是：①列出源对象；②执行相应算法（状态消除/可区分表/PDA 的 ID 推演/CFG 推导/PCP 搜索等）；③每一步记录新状态、集合或配置；④用接受条件或不变量核对最终结果。 由于公开版不直接复制教材图表，精确的状态名、边权和表项以所标 PDF 页为准；算法步骤在这里完整给出，学习时可逐行对照源页复算。
Common mistakes
- 跳过量词、边界条件或接受方式；
- 把“存在一种构造”误写成“任意构造都成立”；
- 图表题未先准确抄录源数据就直接计算。
1.7 习题 8.3.1
Source: textbook PDF p.247
Problem（教材题意释义）
用状态存储、多道、子程序等技术重新设计习题 8.2.2 的图灵机。
Topic
图灵机
方法导引（通用，非本题具体答案）
先给出高层算法，再说明如何落实为有限控制与带操作。典型套路是多次扫描并把已处理符号做标记；多带机可把输入、工作区和计数分别放在不同带上；NTM 只把“猜一个候选”作为分支，随后仍需确定地验证。 正确性用循环不变量说明每轮扫描后哪些位置已经匹配/计数，停机性用每轮至少永久标记一个符号或严格缩小未处理区间证明。 要证明模型等价，则给出编码模拟：把多个带/多个头/二维坐标编码到一条带上，每个原机一步由有限次扫描模拟。
Common mistakes
- 跳过量词、边界条件或接受方式；
- 把“存在一种构造”误写成“任意构造都成立”；
- 图表题未先准确抄录源数据就直接计算。
1.8 习题 8.3.2
Source: textbook PDF p.247
Problem（教材题意释义）
实现“右移一格”子程序：把读头右侧内容整体右移并把读头送回原位。
Topic
按教材定义构造 + 正确性证明
方法导引（通用，非本题具体答案）
按题目定义直接建立形式化对象，并使用本章相应的标准构造或归纳证明。先写清楚输入、目标和不变量，再逐步给出构造；证明正确性时分别证明“构造出的对象不会接受/生成错误实例”和“每个合法实例都能被接受/生成”。 若题目是算法题，还要说明停机性与渐近复杂度；若是反例题，优先寻找最短、结构最简单的反例。
Common mistakes
- 跳过量词、边界条件或接受方式；
- 把“存在一种构造”误写成“任意构造都成立”；
- 图表题未先准确抄录源数据就直接计算。
1.9 习题 8.3.3
Source: textbook PDF p.247
Problem（教材题意释义）
写跳过连续 0 的子程序，并用它识别不存在相邻 1 的二进制串。
Topic
按教材定义构造 + 正确性证明
方法导引（通用，非本题具体答案）
按题目定义直接建立形式化对象，并使用本章相应的标准构造或归纳证明。先写清楚输入、目标和不变量，再逐步给出构造；证明正确性时分别证明“构造出的对象不会接受/生成错误实例”和“每个合法实例都能被接受/生成”。 若题目是算法题，还要说明停机性与渐近复杂度；若是反例题，优先寻找最短、结构最简单的反例。
Common mistakes
- 跳过量词、边界条件或接受方式；
- 把“存在一种构造”误写成“任意构造都成立”；
- 图表题未先准确抄录源数据就直接计算。
1.10 习题 8.4.1
Source: textbook PDF p.252
Problem（教材题意释义）
为 8.2.2 的三个语言设计多带 TM，并尽量达到线性时间。
Topic
TM
方法导引（通用，非本题具体答案）
先给出高层算法，再说明如何落实为有限控制与带操作。典型套路是多次扫描并把已处理符号做标记；多带机可把输入、工作区和计数分别放在不同带上；NTM 只把“猜一个候选”作为分支，随后仍需确定地验证。 正确性用循环不变量说明每轮扫描后哪些位置已经匹配/计数，停机性用每轮至少永久标记一个符号或严格缩小未处理区间证明。 要证明模型等价，则给出编码模拟：把多个带/多个头/二维坐标编码到一条带上，每个原机一步由有限次扫描模拟。
Common mistakes
- 跳过量词、边界条件或接受方式；
- 把“存在一种构造”误写成“任意构造都成立”；
- 图表题未先准确抄录源数据就直接计算。
1.11 习题 8.4.2
Source: textbook PDF p.253
Problem（教材题意释义）
对教材给定 NTM 转移表，列出输入 01、011 的所有/关键可达 ID。
Topic
TM
方法导引（通用，非本题具体答案）
把教材页中的状态、边、权值或产生式先完整抄成一个有限表，然后严格按本章算法逐步计算；不要凭图形直觉跳步。 本题的可复现做法是：①列出源对象；②执行相应算法（状态消除/可区分表/PDA 的 ID 推演/CFG 推导/PCP 搜索等）；③每一步记录新状态、集合或配置；④用接受条件或不变量核对最终结果。 由于公开版不直接复制教材图表，精确的状态名、边权和表项以所标 PDF 页为准；算法步骤在这里完整给出，学习时可逐行对照源页复算。
Common mistakes
- 跳过量词、边界条件或接受方式；
- 把“存在一种构造”误写成“任意构造都成立”；
- 图表题未先准确抄录源数据就直接计算。
1.12 习题 8.4.3
Source: textbook PDF p.253
Problem（教材题意释义）
设计 NTM 处理教材的重复子串/带 # 分隔整数索引等三个语言。
Topic
TM
方法导引（通用，非本题具体答案）
先给出高层算法，再说明如何落实为有限控制与带操作。典型套路是多次扫描并把已处理符号做标记；多带机可把输入、工作区和计数分别放在不同带上；NTM 只把“猜一个候选”作为分支，随后仍需确定地验证。 正确性用循环不变量说明每轮扫描后哪些位置已经匹配/计数，停机性用每轮至少永久标记一个符号或严格缩小未处理区间证明。 要证明模型等价，则给出编码模拟：把多个带/多个头/二维坐标编码到一条带上，每个原机一步由有限次扫描模拟。
Common mistakes
- 跳过量词、边界条件或接受方式；
- 把“存在一种构造”误写成“任意构造都成立”；
- 图表题未先准确抄录源数据就直接计算。
1.13 习题 8.4.4
Source: textbook PDF p.253
Problem（教材题意释义）
根据教材给定 NTM 规则刻画其接受语言。
Topic
TM
方法导引（通用，非本题具体答案）
先给出高层算法，再说明如何落实为有限控制与带操作。典型套路是多次扫描并把已处理符号做标记；多带机可把输入、工作区和计数分别放在不同带上；NTM 只把“猜一个候选”作为分支，随后仍需确定地验证。 正确性用循环不变量说明每轮扫描后哪些位置已经匹配/计数，停机性用每轮至少永久标记一个符号或严格缩小未处理区间证明。 要证明模型等价，则给出编码模拟：把多个带/多个头/二维坐标编码到一条带上，每个原机一步由有限次扫描模拟。
Common mistakes
- 跳过量词、边界条件或接受方式；
- 把“存在一种构造”误写成“任意构造都成立”；
- 图表题未先准确抄录源数据就直接计算。
1.14 习题 8.4.5
Source: textbook PDF p.253
Problem（教材题意释义）
在只有一个 $ 标记的空白带上设计 NTM 找到 $；再说明如何确定化。
Topic
TM
方法导引（通用，非本题具体答案）
先给出高层算法，再说明如何落实为有限控制与带操作。典型套路是多次扫描并把已处理符号做标记；多带机可把输入、工作区和计数分别放在不同带上；NTM 只把“猜一个候选”作为分支，随后仍需确定地验证。 正确性用循环不变量说明每轮扫描后哪些位置已经匹配/计数，停机性用每轮至少永久标记一个符号或严格缩小未处理区间证明。 要证明模型等价，则给出编码模拟：把多个带/多个头/二维坐标编码到一条带上，每个原机一步由有限次扫描模拟。
Common mistakes
- 跳过量词、边界条件或接受方式；
- 把“存在一种构造”误写成“任意构造都成立”；
- 图表题未先准确抄录源数据就直接计算。
1.15 习题 8.4.6
Source: textbook PDF p.253
Problem（教材题意释义）
设计双带 TM 识别 #0=#1，并让第二带只保存计数差/符号。
Topic
TM
方法导引（通用，非本题具体答案）
先给出高层算法，再说明如何落实为有限控制与带操作。典型套路是多次扫描并把已处理符号做标记；多带机可把输入、工作区和计数分别放在不同带上；NTM 只把“猜一个候选”作为分支，随后仍需确定地验证。 正确性用循环不变量说明每轮扫描后哪些位置已经匹配/计数，停机性用每轮至少永久标记一个符号或严格缩小未处理区间证明。 要证明模型等价，则给出编码模拟：把多个带/多个头/二维坐标编码到一条带上，每个原机一步由有限次扫描模拟。
Common mistakes
- 跳过量词、边界条件或接受方式；
- 把“存在一种构造”误写成“任意构造都成立”；
- 图表题未先准确抄录源数据就直接计算。
1.16 习题 8.4.7
Source: textbook PDF p.253
Problem（教材题意释义）
用额外工作带模拟栈 push/pop 接口，说明多带 TM 如何实现栈机。
Topic
TM
方法导引（通用，非本题具体答案）
先给出高层算法，再说明如何落实为有限控制与带操作。典型套路是多次扫描并把已处理符号做标记；多带机可把输入、工作区和计数分别放在不同带上；NTM 只把“猜一个候选”作为分支，随后仍需确定地验证。 正确性用循环不变量说明每轮扫描后哪些位置已经匹配/计数，停机性用每轮至少永久标记一个符号或严格缩小未处理区间证明。 要证明模型等价，则给出编码模拟：把多个带/多个头/二维坐标编码到一条带上，每个原机一步由有限次扫描模拟。
Common mistakes
- 跳过量词、边界条件或接受方式；
- 把“存在一种构造”误写成“任意构造都成立”；
- 图表题未先准确抄录源数据就直接计算。
1.17 习题 8.4.8
Source: textbook PDF p.253
Problem（教材题意释义）
比较三种用单带图灵机模拟 k 带图灵机的编码方案：计算 5 带、7 符号情形所需带字母表大小，并分析将带头位置放到额外道或通过整体平移对齐带头的优缺点。
Topic
图灵机
方法导引（通用，非本题具体答案）
先给出高层算法，再说明如何落实为有限控制与带操作。典型套路是多次扫描并把已处理符号做标记；多带机可把输入、工作区和计数分别放在不同带上；NTM 只把“猜一个候选”作为分支，随后仍需确定地验证。 正确性用循环不变量说明每轮扫描后哪些位置已经匹配/计数，停机性用每轮至少永久标记一个符号或严格缩小未处理区间证明。 要证明模型等价，则给出编码模拟：把多个带/多个头/二维坐标编码到一条带上，每个原机一步由有限次扫描模拟。
Common mistakes
- 跳过量词、边界条件或接受方式；
- 把“存在一种构造”误写成“任意构造都成立”；
- 图表题未先准确抄录源数据就直接计算。
1.18 习题 8.4.9
Source: textbook PDF p.253
Problem（教材题意释义）
定义 k 头单带图灵机（k 个读写头同时作用于同一条带），证明 k 头图灵机与普通图灵机接受的语言完全相同。
Topic
图灵机
方法导引（通用，非本题具体答案）
先给出高层算法，再说明如何落实为有限控制与带操作。典型套路是多次扫描并把已处理符号做标记；多带机可把输入、工作区和计数分别放在不同带上；NTM 只把“猜一个候选”作为分支，随后仍需确定地验证。 正确性用循环不变量说明每轮扫描后哪些位置已经匹配/计数，停机性用每轮至少永久标记一个符号或严格缩小未处理区间证明。 要证明模型等价，则给出编码模拟：把多个带/多个头/二维坐标编码到一条带上，每个原机一步由有限次扫描模拟。
Common mistakes
- 跳过量词、边界条件或接受方式；
- 把“存在一种构造”误写成“任意构造都成立”；
- 图表题未先准确抄录源数据就直接计算。
1.19 习题 8.4.10
Source: textbook PDF p.253
Problem（教材题意释义）
定义二维图灵机（带为二维无穷网格，带头可上下左右移动），证明二维图灵机与普通图灵机接受的语言完全相同。
Topic
图灵机
方法导引（通用，非本题具体答案）
先给出高层算法，再说明如何落实为有限控制与带操作。典型套路是多次扫描并把已处理符号做标记；多带机可把输入、工作区和计数分别放在不同带上；NTM 只把“猜一个候选”作为分支，随后仍需确定地验证。 正确性用循环不变量说明每轮扫描后哪些位置已经匹配/计数，停机性用每轮至少永久标记一个符号或严格缩小未处理区间证明。 要证明模型等价，则给出编码模拟：把多个带/多个头/二维坐标编码到一条带上，每个原机一步由有限次扫描模拟。
Common mistakes
- 跳过量词、边界条件或接受方式；
- 把“存在一种构造”误写成“任意构造都成立”；
- 图表题未先准确抄录源数据就直接计算。
1.20 习题 8.5.1
Source: textbook PDF p.259
Problem（教材题意释义）
在最多两个计数器的限制下，设计计数器机接受教材四个语言：n≥m、m≥n、i=j或i=k、三者至少两个相等。
Topic
按教材定义构造 + 正确性证明
方法导引（通用，非本题具体答案）
先给出高层算法，再说明如何落实为有限控制与带操作。典型套路是多次扫描并把已处理符号做标记；多带机可把输入、工作区和计数分别放在不同带上；NTM 只把“猜一个候选”作为分支，随后仍需确定地验证。 正确性用循环不变量说明每轮扫描后哪些位置已经匹配/计数，停机性用每轮至少永久标记一个符号或严格缩小未处理区间证明。 要证明模型等价，则给出编码模拟：把多个带/多个头/二维坐标编码到一条带上，每个原机一步由有限次扫描模拟。
Common mistakes
- 跳过量词、边界条件或接受方式；
- 把“存在一种构造”误写成“任意构造都成立”；
- 图表题未先准确抄录源数据就直接计算。
1.21 习题 8.5.2
Source: textbook PDF p.259
Problem（教材题意释义）
证明带右端标记的单栈机若确定，则不比 DPDA 更强；把栈符号扩展为 (X,S) 状态集合编码。
Topic
PDA；DPDA
方法导引（通用，非本题具体答案）
先明确栈不变量：栈内容应该编码尚未匹配的输入数量或待展开的文法变量。设计转移时按输入阶段分状态，压栈阶段只增加相应标记，匹配阶段每读一个符号弹出一个标记。 终态接受与空栈接受的转换使用新的底栈标记和新起始/终止状态；CFG→PDA 让栈顶变量按产生式做 ε 展开，栈顶终结符与输入相同则匹配弹出。 PDA→CFG 则用变量 [pXq] 表示从状态 p、栈顶 X 出发最终弹出 X 并到 q 的所有输入串，并按转移组合产生式。
Common mistakes
- 跳过量词、边界条件或接受方式；
- 把“存在一种构造”误写成“任意构造都成立”；
- 图表题未先准确抄录源数据就直接计算。