Automata Theory 简明教程

多轨图灵机是多磁带图灵机的特定类型，它包含多个磁道，但只有一个磁头可以读取和写入所有磁道。在此，单个磁头可以一步从 n 个磁道中读取 n 个符号。它接受递归可枚举语言，就像普通单轨单带图灵机所接受的一样。

多轨图灵机可以正式描述为一个 6 元组 (Q, X, ∑, δ, q0, F)，其中 −

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