Vince Jiang

CSCI3130 / 课程伴读 · 本站更新

CSCI3130 L09 Part 2 图灵机组合

课程：CSCI3130 Formal Languages and Automata Theory · 资料包，学期待核 本讲：L09 Part 2 图灵机组合 · 原件 L09-图灵机-资料包.pdf（本地课件） p.98–103 定位：以明确带布局和控制入口组合已有计算模块。 前后：上一份 L09-P1-标准图灵机与函数.md · 下一份 L09-P3-图灵论题.md

p.98 Outline；p.99 Combining Turing Machines分节页。

模块不仅传值，也传带布局（p.100–101）【新】

p.100 方框把TM概括为输入到输出，但实际连接时下一模块看到的是同一条带与当前读头，接口必须约定编码及头的位置。

题面（本讲 · Example 9.12 · p.101；公式按讲义重排）

p.101 f(x,y)=x+yf(x,y)=x+y if x≥yx\ge y, 00 if x<yx<y.

图先调用Comparer C；若x≥y，转Adder A；否则转Eraser E。图下配置明确比较后仍保留原来的 w(x)0w(y)w(x)0w(y)。这不能直接使用上一部分会擦输入只输出0/1的比较机：必须让比较模块保存原始数据或在临时区做标记后恢复。补充演示x=3,y=2，比较分支进入加法输出5的一元编码；x=1,y=2，擦除并输出约定的0。等号归加法支，与上一例“严格大于”接口不同。

不移动头的条件跳转如何实现（p.102）

题面（本讲 · Example 9.13 · p.102）

p.102 Consider the macroinstruction

if a then qj else qk,

标准模型每步必须左右移，所以先读当前符号：若a则保持a并右移到专用中间态qj0，否则保持原符号并右移到qk0。中间态对任意带符号c都保持c、左移到目标qj或qk。两步后一格未改、头回原位，只有控制状态改变。中间态必须是新名字，避免与已有规则冲突。这里a是被检测的字母，不是“任意输入”的占位说法。

p.102 的宏展开公式：对于使用这个条件宏的入口 qi，使用两个新中间态 rj、rk：

δ(qi,a)=(rj,a,R),δ(qi,b)=(rk,b,R)(b∈Γ∖{a}),δ(rj,c)=(qj,c,L)(c∈Γ),δ(rk,c)=(qk,c,L)(c∈Γ). \begin{aligned} \delta(q_i,a)&=(r_j,a,R),\\ \delta(q_i,b)&=(r_k,b,R)\quad(b\in\Gamma\setminus\{a\}),\\ \delta(r_j,c)&=(q_j,c,L)\quad(c\in\Gamma),\\ \delta(r_k,c)&=(q_k,c,L)\quad(c\in\Gamma). \end{aligned}

第二步必须覆盖空白在内的全部 Γ，因为原读头若在非空区最右一格，右移后会正好看到空白。课件写“for all qi”，应理解为各使用这个宏的入口各自按需求展开，不能用同一套条件跳转覆盖整台机器的其他已有规则。

乘法是受控重复复制（p.103）

题面（本讲 · Example 9.14 · p.103）

p.103 Design a Turing machine that multiplies two positive integers in unary notation

原图输入从左到右为两个0，再y的一元串，再0，再x的一元串，即 00,1y0,1x00,1^y0,1^x。每轮把x中一个未处理1标a，再把最左0替换成“0后接一份y”，在左侧结果区添y个1；重复到x无未处理1，最后把a恢复1。图的终局仍保留y和x，产品位于最左两个分隔符之间，不是整条带只剩乘积。

补充算一遍（数字为演示自取）：x=2,y=3，初带 00111011。首轮x标一个a，结果区添111，带为 011101110a1；次轮再添111，带为 011111101110aa；恢复a后为 01111110111011。最左结果区恰6个1，等于2×3。每轮已标x位数增加1，至多x轮，故停机。复制y时须用临时记号逐位复制并恢复，插入通过右移有限后缀实现；若接口要求仅输出乘积，可再擦除保留的x、y区并归位，这是原图之外的清理步骤。

考试角度：（C 级 通识）常见考法是指出模块之间的编码、头位置、输入保留条件，或把宏动作展开为有限标准转移。

把模块接口写成前置与后置条件（补充）

比较模块 C 的前置条件是带上有合法 1x01y1^x01^y 且头在规定入口；本题需要的后置条件有三项：控制状态说明比较结果、原输入仍可供加法使用、读头已回到加法入口。只满足第一项的“输出真假”机器不能直接拼接 A。若用标记配对比较，就需恢复所有标记；若用复制工作区，就需标清哪段是原输入、哪段是临时区，并在返回前清理或隔离临时数据。

对乘法，第 k 轮后的不变量是结果区有 ky 个1、x 区有 k 个已处理标记、y 区恢复到原样。k=0 时结果空；一轮只挑一个新的 x 位并复制一整份 y，使三项同时变为 k+1 对应状态。k=x 时结果 xy，循环停止。若复制一次 y 后不恢复它，下轮读到的是临时标记而非原数，模块串接就破坏前置条件；若把新输出当成未处理 x，又会失去终止度量。

自检：两个正确的 TM 子程序直接连终态和初态，整体就一定正确吗？

前一模块的后置条件是否正好满足后一模块的前置条件？

展开推理与答案

不一定。编码、头位置、带上残留符号或数据是否保留，都可能不匹配。先证明接口相容，再组合各自的正确性与停机性，才能得到整体结论；单独模块正确并不消除连接协议。

本讲核心考点

  • 条件组合需要保留原参数（p.100–101，C 级）。
  • 两步实现不移头条件跳转（p.102，C 级）。
  • 乘法复制次数与工作区布局（p.103，C 级）。

附录

本部分没有需要另列的推导；定义与算例在相应页段内。

来源与证据

历史版本考试证据（本次未重新读取全部试卷）：读了 HW01-2025T1-题目.pdf、HW01-2026T1-题目.pdf、HW02-2025T1-题目-更新.pdf、HW03-2025T1-题目.pdf、HW04-2025T1-题目.pdf、HW05-2025T1-题目.pdf、期中练习-含解答-学期待核.pdf、期末-2022T1-资料包.pdf、Final-Exam-2023T1-题目.pdf、Final-Exam-2024T1-题目.pdf、Final-Exam-2025T1-题目.pdf、期末-2023T1-资料包.pdf、期末-2024未核-资料包.pdf；未识别用途的 PDF：无

  • 原件：L09-图灵机-资料包.pdf（本地课件），PDF p.98–103。

  • 本次独立学习修订：核对本讲110页文本，视觉复核 p.20、41、55、75、93、101–103、105、110；按原转移表实际计算并验证13步配对、12步加法运行。