多帶圖靈機

多帶圖靈機圖靈機類似,唯一的不同在於它可以有 條紙帶,每條紙帶上 都有一個讀寫頭。其狀態轉移函數 修改為:

此處 是帶子的數目。表達式

其中 = L 或 R, 說明若機器處於狀態 , 讀寫頭 所讀出的符號分別為, 則轉移到新狀態 , 將讀寫頭 下的符號分別修改為 , 並將讀寫頭 按照 所指示的方向移動, 讀寫頭 向左移, 讀寫頭 向右移。

可以證明,對於任意一個多帶圖靈機 ,存在一個單帶圖靈機 ,滿足