非确定型图灵机(non-deterministic Turingmachine)确定型图灵机的一种推广。设P为一个由图灵机指令组成的有穷集合，P不一定满足相容性条件，如果把P作为程序，依类似于确定型图灵机的模式进行运行，则可能会在某个时刻有两条或更多的指令可以用，而它们所规定的动作又不一致。例如P中含有qaBq, BR和qoBq1BL两条指令。则当内部状态为q。且所指单元为空白时，这两条指令都可用，但一个要右移，另一个则要左移。机便称为非确定型图灵机.对不确定型图灵机M来说，对同一个输入可能有不同的运行过程。