[拼音]：duodai tulingji moxing

[外文]：multitape Turing machine model

计算复杂性理论中常用的一种计算模型，它是简单图灵机的一种推广。多带图灵机由一个有穷控制器、一条输入带、一条输出带和 κ条工作带组成。每条带上有一个读写头与有穷控制器相连。每条带都被分成一个个的方格，在每个方格上可以写下一个字母，这些字母均取自一个字母表∑。有穷控制器在任何时候都处在某个状态q，而q属于某个有穷状态 Q。在任何一个时刻，机器总是根据自己目前状态q∈Q以及它的输入带头和工作带头正在扫视κ＋1个符号的情况来决定下面三个动作：

（1）下一步应该转向Q中的哪个状态；

（2）应该把当前扫视的κ条工作带和输出带上的符号分别改成什么符号(输入带上符号不改写)；

（3）把这 κ＋2个带头各自向左还是向右移一格（也可以不动）。一个图灵机就是从上面两个条件到三个动作的一个具体规定。这个规定就是图灵机的程序，可以用列表的方法给出。开始时，机器处在一个特定的状态q0∈Q。原始数据是一个长度为n的符号串，放在输入带上，输入带头指向该串的最左符号，其余各带全为空白。然后机器严格按规定（程序）一步步动作下去，一直到没有定义而停机。这时输出带上的内容即被认为是计算的结果。对于长度为n的输入，机器从开始到停机的总步数称为串行时间；所用过的工作带上的方格数称为空间；从开始到停机各工作带头改变方向的总次数称为巡回。它们都是n的函数。

严正声明：本文由历史百科网注册或游客用户成业自行上传发布关于» 多带图灵机模型的内容，本站只提供存储，展示，不对用户发布信息内容的原创度和真实性等负责。请读者自行斟酌。同时如内容侵犯您的版权或其他权益，请留言并加以说明。站长审查之后若情况属实会及时为您删除。同时遵循 CC 4.0 BY-SA 版权协议，尊重和保护作者的劳动成果，转载请标明出处链接和本声明内容：作者：成业；本文链接：https://www.freedefine.cn/wenzhan/59680.html