Alternating Turing machine
In computational complexity theory, an alternating Turing machine is a non-deterministic Turing machine with a rule for accepting computations that generalizes the rules used in the definition of the complexity classes NP and co-NP.
The definition of NP uses the existential mode of computation: if any choice leads to an accepting state, then the whole computation accepts. The definition of co-NP uses the universal mode of computation: if all choices lead to an accepting state, then the whole computation accepts. An alternating Turing machine (or to be more precise, the definition of acceptance for such a machine) alternates between these modes.
An alternating Turing machine is a non-deterministic Turing machine whose states are divided into two sets: existential states and universal states. An existential state is accepting if some transition leads to an accepting state; a universal state is accepting if every transition leads to an accepting state. (Thus a universal state with no transitions accepts unconditionally; an existential state with no transitions rejects unconditionally). The machine as a whole accepts if the initial state is accepting.
An alternating Turing machine with k alternations is an alternating Turing machine which switches from an existential to a universal state or vice versa no more than k-1 times. (It is an alternating Turing machine whose states are divided into k sets. The states in even-numbered sets are universal and the states in odd-numbered sets are existential (or vice versa). The machine has no transitions between a state in set i and a state in set j < i.)
For example, consider the Boolean function f and a number n, determine if there is a circuit with at most n gates that computes the same function f. An alternating Turing machine, with one alternation, starting in an existential state, can solve this problem in polynomial time (by guessing a circuit B with at most n states, then switching to a universal state, guessing an input, and checking that the output of B on that input matches the output of A on that input).
An alternating Turing machine, with k alternations, starting in an existential (respectively, universal) state can decide all the problems in the class <math>\Sigma_k\rm{P}<math> (respectively, <math>\Pi_k\rm{P}<math>) in polynomial time. See the polynomial hierarchy article.
An alternating Turing machine with unlimited alternations can decide all the problems in the class PSPACE in polynomial time.
