Vince Jiang

CSCI3130 / 课程伴读 · 本站更新

CSCI3130 L09 Part 4 真减法小测

课程：CSCI3130 Formal Languages and Automata Theory · 资料包，学期待核 本讲：L09 Part 4 真减法小测 · 原件 L09-图灵机-资料包.pdf（本地课件） p.110 定位：补全原课件末尾的函数构造题，明确零值编码与输出清理。 前后：上一份 L09-P3-图灵论题.md

截断为零的减法（p.110）

题面（本讲 · Short Quiz · p.110；公式按讲义重排）

p.110 Design a TM that can compute proper subtraction. That is m–n.

m–n if m > n

m–n = 0 if m < n

原页没有单列m=n；按proper subtraction通常含义，本解明确补上等号结果0，即 max⁡(m−n,0)\max(m-n,0)。采用本讲一元编码，输入 1m01n1^m01^n，输出 1max⁡(m−n,0)01^{\max(m-n,0)}0，其中最后0是结果结束符，故零结果编码为单个0。

构造分三阶段。第一，在右数找一个未标1并标Y，再回左数找一个未标1标X；找得到则继续下一轮，找不到说明n尚有需求但m已耗尽，转“结果0”清理。第二，若右数已无未标1，所有n次抵消完成，左数剩余未标1的个数就是m−n；如也无剩则结果0。第三，擦去分隔符、X、Y工作痕迹，将剩余1搬到连续输出区，尾端写0，头回左端停机。每个阶段的左右扫描以分隔符或边界标记结束，有限符号与阶段可编码成有限控制状态。

补充算例（数字为演示自取）：m=5,n=3，三轮后左数为XXX11、右数YYY，剩两个1，整理得110，表示2；m=2,n=4，第三次需求找不到左1，清理得0；m=n=2，两轮后左右都无未标1，同样得0。每轮至少标掉右边一个1，所以不超过n轮，加上有限区间扫描与清理，总会停机。

容易漏的是输出清理：仅留下“左数还剩两个1”并没有兑现题目计算函数的接口，必须说明其他带符号如何处理，以及头最终停在哪里。

考试角度：（C 级 通识）常见考法是分别检查m>n、m=n、m<n，并写出有限循环的不变量与终止理由。

考试角度：（A 级：Final-Exam-2024T1-题目.pdf Q7；期末-2024未核-资料包.pdf Q7；Final-Exam-2025T1-题目.pdf Q6，对应截断减二函数；扫描件视觉读取。）见附录 A1。

用剩余需求解释两种退出（补充）

完整配对 k 次后，左边已有 k 个 X、右边已有 k 个 Y，其余原始1分别有 m−k 与 n−k 个。若右边先空，k=n，所以左边剩 m−n；若准备处理第 k+1 个右1却左边已空，则 k=m<n，输出应截断为0。m=n 时在完成最后一对后首先进入“右边无剩余”的分支，剩余量也为0，不需要第三套碰运气的判断。

实现清理时可以把剩余左1复制到一个明确的输出区，再擦掉原参数、分隔符和标记区，最后回到输出起点。对 m=n 或 m<n，输出区应只写一个0，而不是完全留空：本页约定零结果为单个结束符0。附录减二题使用另一种编码，空串表示数值0；两道题都可以自洽，但不能把附录的零输出悄悄套进本页接口。

自检：输入编码为单个 0 时，本页机器应输出什么？

在 1ᵐ01ⁿ 编码里，这对应哪两个数？

展开推理与答案

它对应 m=n=0。没有任何待匹配1，差值为0，因此仍输出单个0并把头置于它上面。不要把“输入没有1”误判成非法空输入；分隔符0已经构成合法编码。

扫描阶段的失败条件也属于构造（p.110）

开始时先检查输入形状恰为一段1、一个0、另一段1；多于一个0或出现其他输入符号应停机拒绝，不让内部扫描误把错误分隔当边界。保留两端临时界标能让左右往返始终在有限工作区结束。配对成功后才开始下一轮；右边刚标的 Y 若找不到左1，则立即进入归零清理，不继续尝试在空白区域寻找不存在的1。这样每种输入布局都有明确出口，伪代码才真正能实现为标准 TM。

本讲核心考点

  • 成对抵消及三种大小关系（p.110，C 级）。
  • 工作带清理、头归位与停机（p.110，C 级）。

附录

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

A1 作业/往年题演练（非讲义内容）：截断减二函数

题面块（Final-Exam-2024T1-题目.pdf（本地课件） · Q7 · p.1；期末-2024未核-资料包.pdf（本地课件）同题；Final-Exam-2025T1-题目.pdf（本地课件） Q6 p.3同题，扫描件视觉读取）：

p.1 Design a Turing machine (pseudo code) that computes the function:

公式按原图重排：

f(x)={x−2x>2,0x≤2. f(x)=\begin{cases}x-2&x>2,\\0&x\leq2.\end{cases}

原题没有指定整数编码，先明确采用一元输入1ˣ、x为非负整数、空串表示0，读头初始在最左输入格；输出同编码，非空结果头回最左格，零结果头在原输入起点空白。若老师另定编码，应调整编码层，不能默默把二进制串当一元数。

伪代码：若初始格空白，直接停机；否则向右越过全部1到第一个空白，左移。擦掉最后一个1，再左移；若当前是1，擦掉它再左移；如果当前已经空白，说明原输入只有一个1，不再擦。随后向左越过所有剩余1，到左侧空白再右移一格，停机。

x=5：11111擦成111□□，回到首1，输出111即3。x=2擦完两格，回原起点输出空串即0；x=1只擦一格；x=0走初始直接停止分支。有限扫描与至多两次擦除保证总停机，所有定义域边界均覆盖。保留最左剩余段使输出无内部空白，不能删中间两位后就声称已得到标准编码。

回到正文：截断减二函数

来源与证据

历史版本考试证据（本次未重新读取全部试卷）：读了 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.110。

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