鮑國寶

[拼音]：duodai tulingji moxing

[英文]：multitape Turing machine model

計算複雜性理論中常用的一種計算模型，它是簡單圖靈機的一種推廣。多帶圖靈機由一個有窮控制器、一條輸入帶、一條輸出帶和 κ條工作帶組成。每條帶上有一個讀寫頭與有窮控制器相連。每條帶都被分成一個個的方格，在每個方格上可以寫下一個字母，這些字母均取自一個字母表∑。有窮控制器在任何時候都處在某個狀態q，而q屬於某個有窮狀態集合 Q。在任何一個時刻，機器總是根據自己目前狀態q∈Q以及它的輸入帶頭和工作帶頭正在掃視κ＋1個符號的情況來決定下面三個動作：

（1）下一步應該轉向Q中的哪個狀態；

（2）應該把當前掃視的κ條工作帶和輸出帶上的符號分別改成什麼符號(輸入帶上符號不改寫)；

（3）把這 κ＋2個帶頭各自向左還是向右移一格（也可以不動）。一個圖靈機就是從上面兩個條件到三個動作的一個具體規定。這個規定就是圖靈機的程式，可以用列表的方法給出。開始時，機器處在一個特定的狀態q0∈Q。原始資料是一個長度為n的符號串，放在輸入帶上，輸入帶頭指向該串的最左符號，其餘各帶全為空白。然後機器嚴格按規定（程式）一步步動作下去，一直到沒有定義而停機。這時輸出帶上的內容即被認為是計算的結果。對於長度為n的輸入，機器從開始到停機的總步數稱為序列時間；所用過的工作帶上的方格數稱為空間；從開始到停機各工作帶頭改變方向的總次數稱為巡迴。它們都是n的函式。