非确定型图灵机

非确定型图灵机(non-deterministic Turingmachine)确定型图灵机的一种推广。设P为一个由图灵机指令组成的有穷集合，P不一定满足相容性条件，如果把P作为程序，依类似于确定型图灵机的模式进行运行，则可能会在某个时刻有两条或更多的指令可以用，而它们所规定的动作又不一致。例如P中含有qaBq， BR和qoBq1BL两条指令。则当内部状态为q。且所指单元为空白时，这两条指令都可用，但一个要右移，另一个则要左移。机便称为非确定型图灵机.对不确定型图灵机M来说，对同一个输入可能有不同的运行过程。如果不加特殊说明，通常所说的图灵机都是确定型图灵机。非确定型图灵机和确定型图灵机的不同之处在于，在计算的每一时刻，根据当前状态和读写头所读的符号，机器存在多种状态转移方案，机器将任意地选择其中一种方案继续运作，直到最后停机为止。