非决定型图灵机 编辑
如果不加特殊说明，通常所说的图灵机都是确定型图灵机。非确定型图灵机和确定型图灵机的不同之处在于，在计算的每一时刻，根据当前状态和读写头所读的符号，机器存在多种状态转移方案，机器将任意地选择其中一种方案继续运作，直到最后停机为止。具体而言，其状态转移函数为
1
相关
在计算复杂性理论内，几率图灵机是一个非决定型图灵机，在每个转折点根据某种概率分布随机选择某种可行的转变。
在计算复杂性理论内，几率图灵机是一个非决定型图灵机，在每个转折点根据某种概率分布随机选择某种可行的转变。
在计算复杂度理论内，UP是一个决定型问题的复杂度类，能以非决定型图灵机在多项式时间内解决，且对任何输入只有至多一条接受的路径。UP包含了P，而且被包含在NP内。
在计算复杂度理论内，复杂度类 NE是一个决定型问题的集合，包含能使用非决定型图灵机，在O 时间内解决的问题。