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