多带图灵机

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