此条目没有列出任何参考或来源。 (2018年9月18日) 维基百科所有的内容都应该可供查证。请协助补充可靠来源以改善这篇条目。无法查证的内容可能会因为异议提出而移除。 |
多带图灵机和图灵机类似,唯一的不同在于它可以有 条纸带,每条纸带上
都有一个读写头。其状态转移函数 修改为:
此处 是带子的数目。表达式
其中 = L 或 R,
说明若机器处于状态 ,
读写头 所读出的符号分别为,
则转移到新状态 ,
将读写头 下的符号分别修改为 ,
并将读写头 按照 所指示的方向移动,
读写头 向左移,
读写头 向右移。
可以证明,对于任意一个多带图灵机 ,存在一个单带图灵机 ,满足 。