多带图灵机

多带模型把输入、临时记录和中间结果分开放置。算法可以一边读原数据，一边写副本，或者保留一个工作带上的位置，同时移动另一个头。这减少了磁带上的来回寻找，却没有增加不可计算的指令。

它与单带图灵机理路图灵机Turing machine通过有限控制、可读写纸带和移动读写头刻画一般算法计算能力的模型。有相同的可计算能力：多带机能忽略额外磁带来执行单带程序；单带机也能编码全部带内容和头位置，逐步模拟多带程序。等价的是最终可计算的函数、可识别和可判定的语言，而不是每一步所需的时间。

两条带如何比较两个字符串 ​

考虑语言 $L=\{w\mathrm{\#}w:w\in \{0,1{\}}^{\ast }\}$。两带机顺序读取第一段 $w$，同时把它复制到第二条带；读到 # 后，让第一条带的头留在第二段开头，把第二条带的头退回副本开头。接着两头同步右移，逐位比较，只有字符始终相同且两段同时结束才接受。

检查缺少分隔符、多个分隔符和长度不等的情况也只需有限扫描。若总输入长度为 $n$，复制、回退和比较各最多扫描 $O(n)$ 个格，总时间为 $O(n)$。

单带机的朴素做法则可能每匹配一位，就在分隔符两侧往返寻找尚未检查的位置，累计达到二次时间。这个对比展示了组织方式带来的便利；仅分析这一个朴素实现，并不能证明所有单带算法都必须同样慢。

单带模拟具体保存什么 ​

把各条带已经使用的有限部分用分隔符拼在一起，并给每条带恰好一个格加上“带头在此”的标记。例如下列状态中，方括号标记的是虚拟读写头，不是实际磁带字符：

带 1：0 [1] 1       带 2：[0] 0
编码：# 0 [1] 1 # [0] 0 #

单带机模拟一步时，先扫描编码区，收集 $k$ 个带头符号。因为 $k$、字母表和被模拟机器都固定，这些信息可以暂存在有限控制器中。随后查转移规则，再用常数次扫描更新写入符号与头标记；虚拟头走出已编码区域时，为相应磁带补入空白格，必要时平移后续编码。

一次扫描不能在看到第一个头时就随意完成转移，因为新动作可能依赖其余磁带头下的符号。“先收齐输入，再统一更新”保持了原来的一步语义。

二次模拟开销从哪里来 ​

长度为 $n$ 的输入上，若原机运行 $t=t(n)$ 步，各个头至多向新位置移动 $t$ 次；固定条数的磁带合起来只需 $O(n+t)$ 个编码格。每次模拟用 $O(n+t)$ 时间扫描、更新或扩展，初始化还需 $O(n)$ 时间，所以朴素构造给出

在复杂性教材通常采用的 $t(n)\ge n$ 约定下，它简化为 $O(t(n{)}^2)$。这里的常数允许依赖固定机器的磁带条数和字母表；不是把任意输入给出的巨大机器描述当作常数。

更精细的模拟需要区分“总共一条带”“一条工作带另加输入输出带”“两条工作带”等模型。不能把某个保留额外磁带的更快模拟结果，直接宣称为严格单带模型的同一上界。

哪些结论保持，哪些需要重新核对 ​

多项式时间经过上述模拟仍是多项式，所以P理路复杂度类 PP · Polynomial time能由确定性算法在输入长度的多项式时间内判定的语言集合。 不依赖在这两种标准模型间的选择。可计算性同样保持，因为每个模拟步骤最终都能完成；即使原机不停止，模拟也只会继续推进，不会凭空得到一个停机答案。

多轨磁带则把一个格存成多个符号的元组，但所有轨道共享同一个物理带头；多带机的各头可以独立移动。二者都便于编码，操作上的便利并不相同。

研究空间复杂性时，还常把只读输入带与工作带分开，工作空间不计输入本身。否则一个长度 $n$ 的输入就占了 $n$ 格，无法表达对数工作空间的算法。磁带是否只读、空间统计哪些带、时间如何计步，都应在模型比较前固定。