多帶圖靈機模型是計算複雜性理論中常用的一種計算模型，它是簡單圖靈機的一種擴展。
基本介紹
- 中文名：多帶圖靈機模型
- 外文名：multitape Turing machine model
- 性質：計算模型
- 組成：一個有窮控制器、一條輸入帶等
組成,工作原理,編程原理,
組成
多帶圖靈機模型由無限長度帶子、讀寫頭和控制器組成。無限長度帶子被分割為若干格，每一格可以寫入有限符號集(
，
，....，
)中的某個符號，或者空格符。讀寫頭可以讀到它所指向的位置中的符號(包括空格符，，控制器處於有限狀態集(
)中的某個狀態，初始時處於初始狀態
。控制器能夠根據指定的規則和讀人的符號，從一個狀態轉換到另一個狀態。停機狀態是一個特殊狀態，圖靈機計算過程正常結束後處於該狀態。讀寫頭和控制器可以在帶子上左右移動，但每一次只能移動一格。
控制器中的規則通過指令指定。指令由以下內容組成。
·控制器當前狀態；
·讀寫頭讀到的符號；
·用於取代讀寫頭當前位置符號的符號（新寫入符號）；
·控制器轉換後的狀態；
·讀寫頭移動方向（左移、右移、保持不動）。
因此，指令可以用五元組(
)表示，其中表示控制器當前狀態，
表示瀆寫頭當前位置讀到的符號（包括空格符），
表示讀寫頭新寫入當前位置的符號（包括空格符），
表示控制器轉換後的狀態，D表示讀寫頭移動方向，其中L表示左移一格，R表示右移一恪。N表示保持不動。控制器每執行一條指令，完成一次操作，該操作的依據是控制器當前狀態和讀寫頭讀到的符號。該操作的結果有三種，一是控制器轉換後的新狀態，二是讀寫頭重新寫入的符號，三是讀寫頭進行的移動。控制器周而復始地執行指令，直到控制器轉換後的新狀態為停機狀態。
工作原理
每條帶上有一個讀寫頭與有窮控制器相連。每條帶都被分成一個個的方格，在每個方格上可以寫下一個字母，這些字母均取自一個字母表∑。有窮控制器在任何時候都處在某個狀態q，而q屬於某個有窮狀態集合 Q。在任何一個時刻，機器總是根據自己目前狀態q∈Q以及它的輸入帶頭和工作帶頭正在掃視κ+1個符號的情況來決定下面三個動作：①下一步應該轉向Q中的哪個狀態;②應該把當前掃視的κ條工作帶和輸出帶上的符號分別改成什麼符號(輸入帶上符號不改寫)；③把這 κ+2個帶頭各自向左還是向右移一格（也可以不動）。一個圖靈機就是從上面兩個條件到三個動作的一個具體規定。
編程原理
這個規定就是圖靈機的程式，可以用列表的方法給出。開始時，機器處在一個特定的狀態q0∈Q。原始數據是一個長度為n的符號串,放在輸入帶上，輸入帶頭指向該串的最左符號，其餘各帶全為空白。然後機器嚴格按規定（程式）一步步動作下去，一直到沒有定義而停機。這時輸出帶上的內容即被認為是計算的結果。對於長度為n的輸入,機器從開始到停機的總步數稱為串列時間；所用過的工作帶上的方格數稱為空間；從開始到停機各工作帶頭改變方向的總次數稱為巡迴。它們都是n的函式。
