多带图灵机

Template:Unreferenced 多带图灵机和图灵机类似，唯一的不同在于它可以有 $k>1$ 条纸带，每条纸带上 都有一个读写头。其状态转移函数 $\delta$ 修改为：

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

此处 $k$ 是带子的数目。表达式

$\delta (q,x_1,x_2,\dots ,x_k)=(q^{\prime },x{\text{'}}_1,x{\text{'}}_2,\dots ,x{\text{'}}_k,m_1,m_2,\dots ,m_k)$

其中 $m_i$ = L 或 R， 说明若机器处于状态 $q$， 读写头 $1,2,\dots ,k$ 所读出的符号分别为$x_1,x_2,\dots ,x_k$， 则转移到新状态 $q^{\prime }$， 将读写头 $1,2,\dots ,k$ 下的符号分别修改为 $x{\text{'}}_1,x{\text{'}}_2,\dots ,x{\text{'}}_k$ ， 并将读写头 $i$ 按照 $m_i$ 所指示的方向移动， $m_i=L$ 读写头 $i$ 向左移， $m_i=R$ 读写头 $i$ 向右移。

可以证明，对于任意一个多带图灵机 $M$ ，存在一个单带图灵机 $M^{\prime }$ ，满足 $L(M)=L(M^{\prime })$。