多帶圖靈機

多帶圖靈機和圖靈機類似，唯一的不同在於它可以有 ${\displaystyle k>1}$ 條紙帶，每條紙帶上 都有一個讀寫頭。其狀態轉移函數 ${\displaystyle \delta }$ 修改為：

${\displaystyle \delta :Q\times \Gamma ^{k}\to Q\times \Gamma ^{k}\times \{L,R\}^{k}}$

此處 ${\displaystyle k}$ 是帶子的數目。表達式

${\displaystyle \delta (q,x_{1},x_{2},\ldots ,x_{k})=(q',x'_{1},x'_{2},\ldots ,x'_{k},m_{1},m_{2},\ldots ,m_{k})}$

其中 ${\displaystyle m_{i}}$ = L 或 R， 說明若機器處於狀態 ${\displaystyle q}$， 讀寫頭 ${\displaystyle 1,2,\ldots ,k}$ 所讀出的符號分別為${\displaystyle x_{1},x_{2},\ldots ,x_{k}}$， 則轉移到新狀態 ${\displaystyle q'}$， 將讀寫頭 ${\displaystyle 1,2,\ldots ,k}$ 下的符號分別修改為 ${\displaystyle x'_{1},x'_{2},\ldots ,x'_{k}}$ ， 並將讀寫頭 ${\displaystyle i}$ 按照 ${\displaystyle m_{i}}$ 所指示的方向移動， ${\displaystyle m_{i}=L}$ 讀寫頭 ${\displaystyle i}$ 向左移， ${\displaystyle m_{i}=R}$ 讀寫頭 ${\displaystyle i}$ 向右移。

可以證明，對於任意一個多帶圖靈機 ${\displaystyle M}$ ，存在一個單帶圖靈機 ${\displaystyle M'}$ ，滿足 ${\displaystyle L(M)=L(M')}$。