跳转到内容

多带图灵机

维基百科,自由的百科全书

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

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

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

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