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:
“But it is found that the machine unmans the user. What he gains in making cloth, he loses in general power. There should be a temperance in making cloth, as well as in eating.”
—Ralph Waldo Emerson (1803–1882)