Alternating Turing machine

In computational complexity theory, an alternating Turing machine (ATM) is a non-deterministic Turing machine (NTM) with a rule for accepting computations that generalizes the rules used in the definition of the complexity classes NP and co-NP. The concept of an ATM was set forth by Chandra and Stockmeyer and independently by Kozen in 1976, with a joint journal publication in 1981. In computational complexity theory, an alternating Turing machine (ATM) is a non-deterministic Turing machine (NTM) with a rule for accepting computations that generalizes the rules used in the definition of the complexity classes NP and co-NP. The concept of an ATM was set forth by Chandra and Stockmeyer and independently by Kozen in 1976, with a joint journal publication in 1981. 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: only if all choices lead to an accepting state does the whole computation accept. 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. Formally, a (one-tape) alternating Turing machine is a 5-tuple M = ( Q , Γ , δ , q 0 , g ) {displaystyle M=(Q,Gamma ,delta ,q_{0},g)} where If M is in a state q ∈ Q {displaystyle qin Q} with g ( q ) = a c c e p t {displaystyle g(q)=accept} then that configuration is said to be accepting, and if g ( q ) = r e j e c t {displaystyle g(q)=reject} the configuration is said to be rejecting. A configuration with g ( q ) = ∧ {displaystyle g(q)=wedge } is said to be accepting if all configurations reachable in one step are accepting, and rejecting if some configuration reachable in one step is rejecting. A configuration with g ( q ) = ∨ {displaystyle g(q)=vee } is said to be accepting when there exists some configuration reachable in one step which is accepting and rejecting when all configurations reachable in one step are rejecting (this is the type of all states in an NTM). M is said to accept an input string w if the initial configuration of M (the state of M is q 0 {displaystyle q_{0}} , the head is at the left end of the tape, and the tape contains w) is accepting, and to reject if the initial configuration is rejecting.