多帶圖靈機

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

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

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

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

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

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