多带图灵机

多带图灵机和图灵机类似，唯一的不同在于它可以有 $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')$。