Editing Turing machine (section)

==Choice c-machines, oracle o-machines==
Early in his paper (1936) Turing makes a distinction between an "automatic machine"—its "motion ... completely determined by the configuration" and a "choice machine":

{{blockquote|...whose motion is only partially determined by the configuration ... When such a machine reaches one of these ambiguous configurations, it cannot go on until some arbitrary choice has been made by an external operator. This would be the case if we were using machines to deal with axiomatic systems.|''The Undecidable'', p. 118}}

Turing (1936) does not elaborate further except in a footnote in which he describes how to use an a-machine to "find all the provable formulae of the [Hilbert] calculus" rather than use a choice machine. He "suppose[s] that the choices are always between two possibilities 0 and 1. Each proof will then be determined by a sequence of choices i<sub>1</sub>, i<sub>2</sub>, ..., i<sub>n</sub> (i<sub>1</sub> = 0 or 1, i<sub>2</sub> = 0 or 1, ..., i<sub>n</sub> = 0 or 1), and hence the number 2<sup>n</sup> + i<sub>1</sub>2<sup>n-1</sup> + i<sub>2</sub>2<sup>n-2</sup> + ... +i<sub>n</sub> completely determines the proof. The automatic machine carries out successively proof 1, proof 2, proof 3, ..." (Footnote ‡, ''The Undecidable'', p.&nbsp;138)

This is indeed the technique by which a deterministic (i.e., a-) Turing machine can be used to mimic the action of a [[nondeterministic Turing machine]]; Turing solved the matter in a footnote and appears to dismiss it from further consideration.

An [[oracle machine]] or o-machine is a Turing a-machine that pauses its computation at state "'''o'''" while, to complete its calculation, it "awaits the decision" of "the oracle"—an entity unspecified by Turing "apart from saying that it cannot be a machine" (Turing (1939), ''The Undecidable'', p.&nbsp;166–168).