多带图灵机
多带图灵机
多带图灵机和图灵机类似，唯一的不同在于它可以有 formula_1 条纸带，每条纸带上
都有一个读写头。其状态转移函数 formula_2 修改为：
formula_3
此处 formula_4 是带子的数目。表达式
formula_5
其中 formula_6 = L 或 R，
说明若机器处于状态 formula_7，
读写头 formula_8 所读出的符号分别为formula_9，
则转移到新状态 formula_10，
将读写头 formula_8 下的符号分别修改为 formula_12 ，
并将读写头 formula_13 按照 formula_6 所指示的方向移动，
formula_15 读写头 formula_13 向左移，
formula_17 读写头 formula_13 向右移。
可以证明，对于任意一个多带图灵机 formula_19 ，存在一个单带图灵机 formula_20 ，满足 formula_21。
本站由爱斯园团队开发维护，感谢那些提出宝贵意见和打赏的网友，没有你们的支持，网站不可能发展到今天，
继往开来，善终如始，我们将继续砥砺前行。
Copyright ©2014 iissy.com, All Rights Reserved.