多轨图灵机

多轨图灵机是一种特殊的多种图灵机，它包含多条磁带，但只有一个磁头在所有磁带上读写。在这里，单个磁头在一步骤中从n条磁道读取n个符号。它接受递归可枚举语言，就像普通的单轨单带图灵机一样。

多轨图灵机可以形式化地描述为一个 6 元组 (Q, X, ∑, δ, q₀, F)，其中：

• Q 是有限的状态集

• X 是磁带字母表

• ∑ 是输入字母表

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

  δ(Q_i, [a₁, a₂, a₃,....]) = (Q_j, [b₁, b₂, b₃,....], 左移或右移)

• q₀ 是初始状态

• F 是最终状态集

注意 - 对于每个单轨图灵机S，都存在一个等价的多轨图灵机M，使得L(S) = L(M)。