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:
“He is no more than the chief officer of the people, appointed by the laws, and circumscribed with definite powers, to assist in working the great machine of government erected for their use, and consequently subject to their superintendence.”
—Thomas Jefferson (1743–1826)