多軌圖靈機



多軌圖靈機是一種特殊的多種圖靈機,它包含多條磁帶,但只有一個磁頭在所有磁帶上讀寫。在這裡,單個磁頭在一步驟中從n條磁軌讀取n個符號。它接受遞迴可列舉語言,就像普通的單軌單帶圖靈機一樣。

多軌圖靈機可以形式化地描述為一個 6 元組 (Q, X, ∑, δ, q0, F),其中:

  • Q 是有限的狀態集

  • X 是磁帶字母表

  • 是輸入字母表

  • δ 是狀態和符號上的關係,其中

    δ(Qi, [a1, a2, a3,....]) = (Qj, [b1, b2, b3,....], 左移或右移)

  • q0 是初始狀態

  • F 是最終狀態集

注意 - 對於每個單軌圖靈機S,都存在一個等價的多軌圖靈機M,使得L(S) = L(M)

廣告