CSCI3130 L10 Part 2 多带与多维存储

课程：CSCI3130 Formal Languages and Automata Theory · 资料包，学期待核 本讲：L10 Part 2 多带与多维存储 · 原件 L10-图灵机变体-资料包.pdf（本地课件） p.40–55 定位：说明复杂存储如何编码为普通带，以及模拟带来的时间开销。 前后：上一份 L10-P1-图灵机的基本变体.md · 下一份 L10-P3-非确定性通用机与可数性.md

p.40 Outline，进入复杂存储。

多带有独立的读头（p.41–43）【新】

p.41 两带各有一个头，p.42 一步同时读(b,f)，分别写(g,d)，第一头左移、第二头右移；控制状态统一从q1变q2。不是先决定第一带动作，再根据改写结果读取第二带，二者的读取都来自执行前配置。p.43 多带模拟单带只需闲置其他带。

每带映射为内容轨和头轨（p.44–46）

p.44 标准单带模拟k带用2k轨，轨数对一台固定机器是常数。p.45 两带示例中第一头在b、第二头在g，各头轨只含一个1。p.46 一轮先完整扫描收集头下字符，再查原转移，再扫描改写内容及移动两个1标志；移动途中用临时标记防止把“刚移过去的头”当成同一轮还需再动一次。每轮结束时编码恢复合法配置。

p.45 原图的四轨排列：第一内容轨 abc、头轨010；第二内容轨 efgh、头轨0010。因此两只逻辑头分别读 b 和 g。参考点 # 各轨对齐，短轨后补空白。p.42 是另一幅例子：所读对为 (b,f)，改成 (g,d)，第一头左移、第二头右移；不要把两页不同的配置拼成同一步。

能力相同仍可能差很多时间（p.47–49）

p.47 得多带与单带同语言类。p.48 对 $a^nb^n$ 展示单带往返配对为平方量级、两带顺序比较为线性量级。p.49 两带可把b段复制到第二带，再分别归位，同步逐字符比较两段长度；每次阶段扫描O(n)，总仍O(n)。单带示例每轮跨越O(n)区域，共O(n)轮，所以O(n²)。原页“back and forth n² times”应理解为总基本移动量级，不是n²轮完整往返；这里没有证明所有单带算法的最优下界。

二维带与有限访问记录（p.50–52）【新】

p.50 二维头可L/R/U/D移动，位置是整数坐标对，图示头在(2,−1)。p.51 二维机用一行即可模拟单带。p.52 单带反向模拟时把访问过的格子列成有限记录，每条带符号与坐标；任一有限时刻访问格数有限，因此不需要一次存完整无限平面。

坐标模拟的一步（p.53–55）

图（p.53）：a在(1,1)、b在(2,−1)、c在(−1,1)，读头指b。下方编码以分隔符存坐标，标出当前记录；图只显示有限片段，不能把未显示坐标当成没有对应格。p.54 若头向上，新坐标(2,0)；扫描表查该坐标，若不存在则新增空白记录，再作为当前格。向左则x减1，向右x加1，上下改y。坐标用有限有符号整数编码，可通过普通带操作加减。

p.55 由每个原步都能有限模拟，二维、多维机不增加接受语言类。有限维数对一台机器固定；不能把无限维或任意实数坐标当作这一定理已涵盖的模型。

考试角度：（C 级 通识）常见考法是区分多轨与多带的头数，并写出“收集旧配置—更新—恢复编码”的模拟顺序。

考试角度：（A 级：HW05-2025T1-题目.pdf Q2，对应双带偶回文。）见附录 A1。

一轮多带更新必须读旧值再写新值（补充）

设第一逻辑头在位置2，第二逻辑头在位置7，当前读到 b、f。模拟机扫描到位置2时可把 b 放进有限控制，但还不能完整查原转移，因为 f 尚未知；扫到位置7取得 f 后，才查表决定两带新符号与两个方向。否则先改第一带再决定第二带，会把原来同时读取的动作改成顺序依赖。

若扫描方向向右、某头标记也要右移，直接擦旧标记并在下一格写普通标记会有风险：下一步扫描又看到它，可能再移动一次。可用“新头标记”与“旧头标记”两类符号，更新阶段只处理旧类，末尾统一把新类还原。每带整轮始终有唯一逻辑头，虽然中间编码允许临时记号。有限个带与有限种符号让这套协议仍能写成有限转移表。

本讲核心考点

• 多带单步与2k轨模拟（p.41–47，C 级）。
• 等能力不等于等时间（p.48–49，C 级）。
• 多维坐标的有限记录（p.50–55，C 级）。

附录

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

A1 作业/往年题演练（非讲义内容）：HW05-2025T1-题目.pdf Q2

题面来自作业p.1；下面涉及辅导图及原解的页码均指 T07-2025T1.pdf（本地课件），不是作业的页码。完整过程同时写入本附录，便于在本讲练习。

题面块（HW05-2025T1-题目.pdf（本地课件） · Q2 · PDF p.1；与该辅导原题一致）：

p.1 Give a formal definition of a two-tape Turing machine; then write programs (Transition Graph or Transition Function) that accept the languages $L=\{ww^R:w\in\{a,b\}^{+}\}$. Assume that $\Sigma=\{a,b\}$ and that the input is initially all on tape 1.

双带机使用两个读写头，转移按 $(q,s_1,s_2)\mapsto(q',t_1,t_2,d_1,d_2)$，方向各为L/R/S；其余有限控制、字母表、初态和终态含义与单带同。带1初始为输入，带2空白，各头在约定起始格。S可由标准动作模拟，不增加能力。

原解每轮标记最左未处理字母为A/B，再将最右未处理字母擦掉并写到带2，带2头向左移。如此带1保存左半，带2最终从左到右保存原右半，随后沿图与相应恢复的左半比较。需要特别留意写入顺序与磁带空间顺序相反；不能只说“把右半倒着取出”就认定磁带上也是倒序。

原状态图的全部转移与实际检验（p.7）

图（p.7）：初态q0，唯一终态q7，状态q0至q7。边标签以两带各自“读;写,方向”并列。以下用□为空白，将原图全部边转成表；s∈{a,b}，大写S是s对应标记A/B，未列者无动作。

看什么：q6同向比较两带，而前段分割将右半按原顺序留在带2。因此这份原图实际检查的是两个相同半串，不是题目要求的反转半串。 输入abab：先标A并取尾b到带2，下一轮标B并取a写到其左，带1恢复为ab，带2为ab，于是接受；但abab不是非空偶回文。abba则恢复出ab/ba，在q6第一格不同而拒绝。原页p.6文字中“in a reverse order”不能消除具体头移动造成的这一问题。

补充（沿原图最小修正）：保留q0至q5的分割。q5已把带1头移到左边空白、带2头在右半副本左边空白。先让带1右移到左半首格；带2右移扫描至副本右侧空白，再左移一格。之后比较时带1向右、带2向左，同字符才继续；带1到右侧空白且带2到左侧空白时接受。这恰检查左半正向与右半反向相同。以下三种状态给出替换q5出口后的完整尾部，带1符号u在扫描带2时保持不动：

其余情况拒绝。输入aa按修正后比较a/a接受；abba比较a/a、b/b接受；abab首个比较a/b拒绝。奇数长度在某轮q2读到大写标记而无动作，拒绝；空串在q0无动作，拒绝，符合w非空。每轮消去两个未处理字符，初始化/扫描有限，最后比较有限，故总停机。

这是原图的完整核对及修正构造，不把印刷图当已验证正确答案。

回到正文：HW05-2025T1-题目.pdf Q2

来源与证据

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

• 原件：L10-图灵机变体-资料包.pdf（本地课件），PDF p.40–55。

• 本次独立学习修订：核对本讲131页文本，并视觉复核 p.20、38、45、53、81、114、128、130–131。