Editing Alternating Turing machine (section)

== Definitions ==

=== Informal description ===

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.

=== 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.

=== Resource bounds ===

When deciding if a configuration of an ATM is accepting or rejecting using the above definition, it is not always necessary to examine all configurations reachable from the current configuration.  In particular, an existential configuration can be labelled as accepting if any successor configuration is found to be accepting, and a universal configuration can be labelled as rejecting if any successor configuration is found to be rejecting.

An ATM decides a [[formal language]] in time <math>t(n)</math> if, on any input of length {{mvar|n}}, examining configurations only up to <math>t(n)</math> steps is sufficient to label the initial configuration as accepting or rejecting.  An ATM decides a language in space <math>s(n)</math> if examining configurations that do not modify tape cells beyond the <math>s(n)</math> cell from the left is sufficient.

A language that is decided by some ATM in time <math>c\cdot t(n)</math> for some constant <math>c>0</math> is said to be in the class <math>\mathsf{ATIME}(t(n))</math>, and a language decided in space <math>c\cdot s(n)</math> is said to be in the class <math>\mathsf{ASPACE}(s(n))</math>.