CSCI3130 T07 · Part 3 二进制串反转

课程：CSCI3130 · 2025T1 本讲：第3部分 / 共4部分 · T07-2025T1.pdf（本地课件） p.8–10 定位：用标记和左侧输出实现反转，最后清理并归位。 前后：上一份 Part 2 · 下一份 Part 4 承接：#L09-05 可计算函数、#L09-08 子程序组合

先标记输入，避免再次处理输出（p.8–9）【已会】

p.8导航，p.9题面及四步思路。

题面块（T07 · Problem 3 · PDF p.9；公式按讲义重排）：

p.9 Construct a Turing machine (Transition Graph or Transition Function) to compute the function: $f(w)=w^R$, where $w\in\{0,1\}^{+}$.

原解先把输入0/1改成x/y，随后每轮找最左未处理x/y，改为z，记住其比特，再到当前非空区左边的第一格空白写入该比特。处理顺序原本从左到右，输出每次添在已有输出左侧，所以顺序反转。z区最后擦除。

算一遍：输入101先变yxy。第一次把最左y标z，在左边写1，得到1zxy；第二次x标z并在已有1左边写0，得到01zzy；第三次y处理后得到101zzz；清理z得到101。为看出方向，自取输入110，依次输出1、11、011，最后是011，前导0必须保留。

原页四步对应四个任务：q0把0/1改成x/y；q2找未处理符号并标z；q3/q4分别记住0/1并向左写输出；返回q2重复。q1负责初始回位，q5负责最后清理，q6为终态。这样正文的过程描述与下表每个状态都有对应，不需另看图寻找某一步由谁执行。

完整状态图及输出归位（p.10）

图（p.10）：初态q0，终态q6，另有q1至q5。全部原图转移如下，□为空白；“保持”表示写回刚读的符号。

看什么：q2跳过已有输出0/1及已处理z，只有x/y触发新一轮；q5既擦z又越过输出至左边界，q6头最终回到输出最左格。不能只产出反转串而把z遗留在结果旁。

每轮未处理x/y数量减1，故n轮后进入清理并停机。第k轮完成后输出等于原串前k个字符的反转，这是正确性不变量。图在空输入上也可能停止，但题目函数域仅非空串；域外行为不影响本题，若要求拒绝空串，可新增起始检查再进入图中流程。原图使用双向无限带，本课程模型支持向输入左侧写输出。

用三块区域证明不会把输出再反转一次（补充）

初始串写成 $b_1\cdots b_n$，每个 $b_i\in\{0,1\}$。处理完 k 个字符、完成向左写入后，非空区从左至右为 $b_k\cdots b_1$、k 个 z、尚未处理的 $b_{k+1}\cdots b_n$ 的 x/y 编码。第一块是最终输出的一部分，第二块是已消耗的输入，第三块才是工作队列。q2 只在第三块的 x/y 上启动新一轮，故不会重新处理输出中的0/1。

当 k=n 时，第三块为空，q2 扫到右侧空白进入清理。q5 向左抹掉全部 z，再原样经过全部输出，直到左边空白；最后右移一格，头正对输出首字符。这样不仅证明带上存在反转串，也证明它是唯一留下的非空内容，且满足后续子程序可接续的头位置约定。前导0是字符串的一部分，不得按二进制整数显示方式删去。

本讲核心考点

• 输入标记与输出分离，停机时清除z并将头放回结果左端（p.8–10，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：无

• 原件：T07-2025T1.pdf（本地课件），PDF p.8–10。

• 本次独立学习修订：核对对应辅导原件全部文本与本篇题面，保留完整规则、转移与证明。视觉复核物理页7、10的全部转移。