多磁帶圖靈機



多磁帶圖靈機有多個磁帶,每個磁帶都有一個單獨的磁頭訪問。每個磁頭可以獨立於其他磁頭移動。最初,輸入在磁帶 1 上,其他磁帶為空白。首先,第一個磁帶被輸入佔用,其他磁帶保持空白。接下來,機器讀取磁頭下連續的符號,並且 TM 在每個磁帶上列印一個符號並移動其磁頭。

Multi-tape Turing Machine

多磁帶圖靈機可以正式描述為一個 6 元組 (Q, X, B, δ, q0, F),其中 -

  • Q 是狀態的有限集合

  • X 是磁帶字母表

  • B 是空白符號

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

    δ: Q × Xk → Q × (X × {左移, 右移, 不移})k

    其中有 k 個磁帶

  • q0 是初始狀態

  • F 是最終狀態的集合

注意 - 每個多磁帶圖靈機都有一個等價的單磁帶圖靈機。

廣告