形式陈述

多带图灵机具有有限条磁带，每条带有独立读写头；一步依据当前状态和各头所见符号，同时写入、移动并改变状态。它与单带 TM 具有相同的可计算能力。若一台 $k$$k$ 带机在 $t(n)$$t(n)$ 步内运行，标准轨道编码可由单带机在 $O(t(n)^2)$$O(t(n{)}^2)$ 时间内模拟；更精细模型可改善常数或对数因子，但不会改变可判定语言类。

直觉

多条磁带像把工作区、输入和临时数据分开放置，算法描述更自然；单带机可以把所有磁带内容编码在一条带上，只是每次寻找各读写头更慢。

例子与边界

复制输入时，两带机可一边扫描输入一边写入第二带；单带机往返标记会更费时。磁带条数必须是模型定义中的固定常数；若随输入免费提供指数多磁带，资源度量会改变。等价性指可计算性，不表示逐步或线性时间等价。只读输入带加若干工作带是空间复杂性中常见约定。

推论与应用

多带模型用于清晰描述通用机、字符串算法和复杂性类；模型鲁棒性说明多项式时间等粗粒度类别不依赖合理的低层磁带组织。

参考资料

• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013，Chs. 0–10。
• Alan M. Turing, “On Computable Numbers, with an Application to the Entscheidungsproblem,” Proceedings of the London Mathematical Society, 1936，Full paper。