英文
non-deterministic Turing machine
简介
确定型图灵机的一种推广.设P为一个由图灵机指令组成的有穷集合，P不一定满足相容性条件，如果把P作为程序，依类似于确定型图灵机的模式进行运行，则可能会在某个时刻有两条或更多的指令可以用，而它们所规定的动作又不一致.例如P中含有q0Bq1BR和q0Bq1BL两条指令.则当内部状态为q0且所指单元为空白时，这两条指令都可用，但一个要右移，另一个则要左移.此时，如果约定可以按其任意一条进行操作，那么以这种P为程序的图灵机便称为非确定型图灵机.对不确定型图灵机M来说，对同一个输入可能有不同的运行过程.与确定型图灵机一样，全体非确定型图灵机可以能行地排成一列：NM0，NM1，NM2，…，NMe，…称之为非确定型图灵机的能行枚举.其e称为NMe的下标.