多轨图灵机

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

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

• Q是有限状态集

• X是磁带字母表

• Σ是输入字母表

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

  δ(Q _i , [a ₁ , a ₂ , a ₃ ,....]) = (Q _j , [b ₁ , b ₂ , b ₃ ,....], Left_shift 或 Right_shift)

• q ₀是初始状态

• F是最终状态的集合

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