Other meanings of Turing machine
Computational theory
An alternating Turing machine (ATM) extends nondeterministic computation by assigning states an existential or universal interpretation. An input is accepted when existential choices can select a successful computation while every branch from a universal state succeeds. This alternating, tree-shaped semantics links machine models to games, quantified logic, and major complexity classes such as PSPACE and the polynomial hierarchy.1
An alternating Turing machine combines existential and universal branching in one computation model. A configuration is labeled existential, universal, accepting, or rejecting; an existential configuration accepts if at least one successor accepts, whereas a universal configuration accepts only if all successors accept. The resulting computation is a finite tree rather than a single path.
This is a refinement of a nondeterministic Turing machine: nondeterminism uses an existential, “some branch” interpretation throughout, while alternation permits the machine to switch between “some” and “every.” A run therefore resembles a two-player game. The existential player chooses successors at existential states, the universal player chooses them at universal states, and the initial position is winning exactly when the input is accepted.
Alternation converts bounds on time and space into strikingly different deterministic complexity bounds. A polynomial-time alternating machine recognizes exactly the languages in PSPACE, while polynomial-space alternation reaches deterministic exponential time under standard resource conventions.
The reason is that a computation tree may have exponentially many nodes even when every branch is polynomially long. A depth-first deterministic simulation can reuse storage between branches, producing a polynomial-space simulation; storing the entire tree instead can require much more space. Conversely, a deterministic polynomial-space computation can be represented by an alternating polynomial-time search through configurations, with existential choices selecting a candidate continuation and universal choices verifying alternatives.
Restricting the number or pattern of alternations yields finer classes. Polynomial-time machines with a bounded number of alternation blocks correspond to levels of the polynomial hierarchy, whose existential and universal layers generalize NP and coNP.1
Alternating computation gives a machine-level formulation of quantified logical search. Existential branching corresponds to choosing a witness, while universal branching checks all assignments or adversarial responses; this makes quantified Boolean formula a canonical complete problem for polynomial-space computation.2
The model is useful for describing planning, protocol verification, games, and adversarial search. A position can be existential when a controller chooses an action and universal when an environment chooses one. Acceptance then expresses the existence of a strategy that succeeds against every permitted response, rather than merely the existence of one favorable path.
Alternation is also a compact description of recursive divide-and-conquer procedures. The machine need not materialize every branch simultaneously: a deterministic simulator can evaluate the acceptance condition recursively, which explains why tree-like computation can have high time complexity but comparatively modest space requirements.
The power of an alternating machine depends strongly on how alternations are counted and how its resource bound is stated. A machine may be measured by total running time on each branch, by the number of alternation switches, or by space used along a branch; these conventions generate related but distinct class definitions.
Alternation also clarifies why nondeterministic and co-nondeterministic reasoning appear together in verification. A universal state is not simply “parallel execution”: its acceptance condition is logical conjunction, so one failing successor rejects the whole configuration. Likewise, an existential state may ignore arbitrarily many failing successors if one successful successor exists.
The formalism is closely related to game semantics, in which computation becomes a contest between a protagonist and an opponent. This perspective extends beyond complexity theory to model checking and controller synthesis, where the central question is whether a winning strategy exists under all relevant environmental choices.3
Complexity-class equalities assume standard multitape or equivalent machine conventions; polynomial factors and encoding details do not change the stated results.
Help improve the encyclopedia. Reports go straight to the site manager.