Editing Alternating Turing machine (section)

===Definition===
{{Unreferenced section|date=October 2013}}
An '''alternating Turing machine with ''k'' alternations''' is an alternating Turing machine that 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'' &lt; ''i''.)

<math>\mathsf{ATIME}(C,j)=\Sigma_j \mathsf{TIME}(C)</math> is the class of languages decidable in time <math>f\in C</math> by a machine beginning in an existential state and alternating at most <math>j-1</math> times. It is called the {{mvar|j}}th level of the <math>\mathsf{TIME}(C)</math> hierarchy.

<math>\mathsf{coATIME}(C,j)=\Pi_j \mathsf{TIME}(C)</math> is defined in the same way, but beginning in a universal state; it consists of the complements of the languages in <math>\mathsf{ATIME}(f,j)</math>.

<math>\mathsf{ASPACE}(C,j)=\Sigma_j \mathsf{SPACE}(C)</math> is defined similarly for space bounded computation.