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.
Read more about Alternating Turing Machine: Example, Complexity Classes and Comparison To Deterministic Turing Machines
Famous quotes containing the word machine:
“Much that is natural, to the will must yield.
Men manufacture both machine and soul,
And use what they imperfectly control
To dare a future from the taken routes.”
—Thom Gunn (b. 1929)