多带图灵机

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

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

• Q是有限状态集

• X是磁带字母表

• B是空白符号

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

  δ: Q × X ^k → Q × (X × {左移, 右移, 无移 }) ^k

  其中有k 个磁带

• q ₀是初始状态

• F是最终状态的集合

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