交替图灵机

交替图灵机（alternating Turing machine），计算机科学技术名词，类似于非确定型图灵机。按如下方式定义的计算模型：每一个转移函数有两个选择，每一个内部状态有一个标签或，中间格局由它的状态标签及下一个格局是否接受来确定，交替图灵机接受一个输入 x 当且仅当初始格局最终是可接受的。