多带图灵机

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

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

其中  = L 或 R，
说明若机器处于状态 ，
读写头  所读出的符号分别为，
则转移到新状态 ，
将读写头  下的符号分别修改为  ，
并将读写头  按照  所指示的方向移动，
 读写头  向左移，
 读写头  向右移。

可以证明，对于任意一个多带图灵机  ，存在一个单带图灵机  ，满足 。

图灵机