[科普中国]-多带图灵机模型

多带图灵机模型是计算复杂性理论中常用的一种计算模型，它是简单图灵机的一种扩展。

组成多带图灵机模型由无限长度带子、读写头和控制器组成。无限长度带子被分割为若干格，每一格可以写入有限符号集(，，....，)中的某个符号，或者空格符。读写头可以读到它所指向的位置中的符号(包括空格符，，控制器处于有限状态集()中的某个状态，初始时处于初始状态。控制器能够根据指定的规则和读人的符号，从一个状态转换到另一个状态。停机状态是一个特殊状态，图灵机计算过程正常结束后处于该状态。读写头和控制器可以在带子上左右移动，但每一次只能移动一格。

控制器中的规则通过指令指定。指令由以下内容组成。

·控制器当前状态；

·读写头读到的符号；

·用于取代读写头当前位置符号的符号（新写入符号）；

·控制器转换后的状态；

·读写头移动方向（左移、右移、保持不动）。

因此，指令可以用五元组()表示，其中表示控制器当前状态，表示渎写头当前位置读到的符号（包括空格符），表示读写头新写入当前位置的符号（包括空格符），表示控制器转换后的状态，D表示读写头移动方向，其中L表示左移一格，R表示右移一恪。N表示保持不动。控制器每执行一条指令，完成一次操作，该操作的依据是控制器当前状态和读写头读到的符号。该操作的结果有三种，一是控制器转换后的新状态，二是读写头重新写入的符号，三是读写头进行的移动。控制器周而复始地执行指令，直到控制器转换后的新状态为停机状态。1

工作原理每条带上有一个读写头与有穷控制器相连。每条带都被分成一个个的方格，在每个方格上可以写下一个字母，这些字母均取自一个字母表∑。有穷控制器在任何时候都处在某个状态q，而q属于某个有穷状态集合 Q。在任何一个时刻，机器总是根据自己目前状态q∈Q以及它的输入带头和工作带头正在扫视κ+1个符号的情况来决定下面三个动作：①下一步应该转向Q中的哪个状态;②应该把当前扫视的κ条工作带和输出带上的符号分别改成什么符号(输入带上符号不改写)；③把这 κ+2个带头各自向左还是向右移一格（也可以不动）。一个图灵机就是从上面两个条件到三个动作的一个具体规定。

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

本词条内容贡献者为:

李岳阳 - 副教授 - 江南大学