非确定型图灵机 编辑
如果不加特殊说明，通常所说的图灵机都是确定型图灵机。非确定型图灵机和确定型图灵机的不同之处在于，在计算的每一时刻，根据当前状态和读写头所读的符号，机器存在多种状态转移方案，机器将任意地选择其中一种方案继续运作，直到最后停机为止。具体而言，其状态转移函数为
1
相关
交替式图灵机是计算复杂度理论中定义的一种非确定型图灵机。与一般非确定型图灵机不同，交替式图灵机将接受语言的规则一般化到NP和反NP。交替式图灵机的概念由Chandra和Stockmeyer于1976年提出。
在计算复杂性理论里面，复杂度类NTIME是一种可以用非确定型图灵机使用O的时间和无限制的空间所能解决的所有决定性问题的集合。
NP这个有名的复杂度类，可以用NTIME来定义如下：
在计算复杂度理论内，NSPACE这个复杂度类是一个决定性问题的集合，里面的问题可以以非确定型图灵机使用O这么多空间，不限制时间来解决。或者，换句话说，这是DSPACE的非确定型版本。
在计算复杂度理论内，复杂度类NEXPTIME是一个决定性问题的集合，包含可以使用非确定型图灵机，使用O
在计算复杂度理论内，复杂度类NEXPTIME是一个决定性问题的集合，包含可以使用非确定型图灵机，使用O
在计算复杂性理论里面，复杂度类NTIME是一种可以用非确定型图灵机使用O的时间和无限制的空间所能解决的所有决定性问题的集合。
NP这个有名的复杂度类，可以用NTIME来定义如下：
交替式图灵机是计算复杂度理论中定义的一种非确定型图灵机。与一般非确定型图灵机不同，交替式图灵机将接受语言的规则一般化到NP和反NP。交替式图灵机的概念由Chandra和Stockmeyer于1976年提出。