多轨图灵机

多轨图灵机是一种特定类型的多磁带图灵机，包含多个轨道，但只有一个磁带头在所有轨道上进行读写。在这里，单个磁带头一步从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)。