多带图灵机

多带图灵机有多个磁带，每个磁带都由一个单独的磁头访问。每个磁头都可以独立于其他磁头移动。最初，输入在磁带 1 上，其他磁带为空白。起初，第一个磁带被输入占用，其他磁带保持空白。接下来，机器读取其头部下方的连续符号，TM 在每个磁带上打印一个符号并移动其头部。

多磁带图灵机可以正式描述为 6 元组 (Q、X、B、δ、q₀、F)，其中 −

• Q 是一组有限的状态

• X 是磁带字母表

• B 是空白符号

• δ 是状态和符号的关系，其中

  δ: Q × X^k → Q × (X × {Left_shift, Right_shift, No_shift })^k

  其中有 k 个磁带

• q₀ 是初始状态

• F 是最终状态的集合

注意 − 每个多磁带图灵机都有一个等效的单磁带图灵机。