Editing Alternating Turing machine (section)

=== Formal definition ===

Formally, a (one-tape) '''alternating Turing machine''' is a 5-[[tuple]] <math>M=(Q,\Gamma,\delta,q_0,g)</math> where
* <math>Q</math> is the finite set of states
* <math>\Gamma</math> is the finite tape alphabet
* <math>\delta:Q\times\Gamma\rightarrow\mathcal{P}(Q\times\Gamma\times\{L,R\})</math> is called the transition function (''L'' shifts the head left and ''R'' shifts the head right)
* <math>q_0\in Q</math> is the initial state
* <math>g:Q\rightarrow\{\wedge,\vee,accept,reject\}</math> specifies the type of each state

If ''M'' is in a state <math>q\in Q</math> with <math>g(q)=accept</math> then that configuration is said to be ''accepting'', and if <math>g(q)=reject</math> the configuration is said to be ''rejecting''.  A configuration with <math>g(q)=\wedge</math> 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 <math>g(q)=\vee</math> is said to be accepting when there exists some configuration reachable in one step that is accepting and rejecting when all configurations reachable in one step are rejecting (this is the type of all states in a classical NTM except the final state).  ''M'' is said to accept an input string ''w'' if the initial configuration of ''M'' (the state of ''M'' is <math>q_0</math>, 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.

Note that it is impossible for a configuration to be both accepting and rejecting, however, some configurations may be neither accepting or rejecting, due to the possibility of nonterminating computations.