多带图灵机

多带图灵机和图灵机类似，唯一的不同在于它可以有 条纸带，每条纸带上都有一个读写头。其状态转移函数 修改为： 此处 是带子的数目。表达式 其中 = L 或 R，说明若机器处于状态 ，读写头 所读出的符号分别为，则转移到新状态 ，将读写头 下的符号分别修改为 ，并将读写头 按照 所指示的方向移动， 读写头 向左移， 读写头 向右移。 可以证明，对于任意一个多带图灵机 ，存在一个单带图灵机 ，满足 。