Vince Jiang

CSCI3130 / 辅导 · 本站更新

CSCI3130 T07 · Part 1 多格移动模拟

课程：CSCI3130 · 2025T1 本讲：第1部分 / 共4部分 · T07-2025T1.pdf（本地课件） p.1–4 定位：把有限转移表中的跳跃动作展开成标准机单步动作。 前后：上一单元 T06 · 下一份 Part 2 承接：#L10-01 配置模拟、#L10-02 停留动作

整讲导航：P1 p.1–4、P2 p.5–7、P3 p.8–10、P4 p.11–12。

标题与Outline（p.1–3）

p.1标题日期2025年11月25日，p.2列四题，p.3高亮Problem 1。后续为多格移动、双带偶回文、反转函数、可数性。

有限跳长用有限状态展开（p.4）【已会】

题面块（T07 · Problem 1 · PDF p.4）：

p.4 Consider a variant of a Turing machine in which the read–write head may move several cells left or right in a single transition. Formally define such a machine, and explain how it can be simulated by a standard Turing machine that moves its head only one cell per step.

原页定义七元组M=(Q,Σ,Γ,δ,q0,qacc,qrej)，转移函数按讲义重排为 δ:Q×Γ→Q×Γ×Z\delta:Q\times\Gamma\to Q\times\Gamma\times\mathbb Z。输出(p,b,k)表示写b、切换p、位移k格，k正向右、负向左、0原地。

虽然整数集合无限，一台机器的Q和Γ有限，转移表只有有限多项，所以真正用到的跳长有一个有限最大值K。模拟时每个表项配自己的中间状态，记住目标p、方向及尚剩几步；路过的字符读到什么写回什么，不再重复初次改写。

算一遍（沿原页例）：δ(q,a)=(p,b,4)。模拟器第一步把a写b并右移，进入“还剩3步”状态；接着三步各保留原格符号并右移，最后进入p，总位移4。k=−3同理连续三次左移。k=0时若标准机只有L/R，可先写b右移到临时态，再原样左移回原格进入p；本课双向无限带允许这一步。

停机接受/拒绝状态原样对应；任何一步有限展开，所以原机停机当且仅当模拟机停机，接受行为相同。反方向标准机只用k=±1已是特例，故能力相等。K是针对固定机器的常数，不能把“输入提供任意跳长的另一模型”混入这个定义。

原页的七元组中，Q为有限状态集，Σ为输入字母表，Γ为含空白的有限带字母表且Σ⊆Γ，q0为初态，qacc/qrej分别为接受/拒绝停机态。δ在非停机状态与带符号上给下一步；停机态不再展开普通动作。写出 Z 作为位移范围并不把状态集变成无限。

在宏步边界比较配置（补充）

设原机在位置 j 读到 a，并执行 (q,a)↦(p,b,4)(q,a)\mapsto(p,b,4)。标准机模拟完成时必须同时满足：状态为 p、读头在 j+4、j 格变成 b、其他所有格保持原内容。中间三步的状态可以不同，读头也暂时不在最终位置；等价要求放在整个宏步结束处，而非要求每一个标准步都对应一个原步骤。

为保证不覆盖路过格，中间态必须对每个带字母 c∈Γc\in\Gamma 定义“读 c、写 c、再向指定方向移一格”。若只替空白写转移，遇到输入中的非空符号就会卡住。不同原表项还须使用互不混淆的中间态，保存各自目标状态和剩余步数。固定机器每步最多使用 max⁡(K,2)\max(K,2) 个标准动作（0位移可用来回两步），所以有限停机和无限运行都被保留。

自检：模拟跳4格时，能否四步都把当前格改写成 b？

原动作究竟写了几个格？

展开推理与答案

不能。原动作只写起点一格；其余三步应原样保留路过格。否则即使终点位置正确，带内容已不同，后续计算也可能改变。配置模拟要同时核对状态、读头和整条带。

本讲核心考点

  • 固定机器的最大跳长有限，模拟需保持路过格符号（p.1–4，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.1–4。

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