Relation To Turing Machines
The Turing computable sets of natural numbers are exactly the sets at level of the arithmetical hierarchy. The recursively enumerable sets are exactly the sets at level .
No oracle machine is capable of solving its own halting problem (a variation of Turing's proof applies). The halting problem for a oracle in fact sits in .
Post's theorem establishes a close connection between the arithmetical hierarchy of sets of natural numbers and the Turing degrees. In particular, it establishes the following facts for all n ≥ 1:
- The set (the nth Turing jump of the empty set) is many-one complete in .
- The set is many-one complete in .
- The set is Turing complete in .
The polynomial hierarchy is a "feasible resource-bounded" version of the arithmetical hierarchy in which polynomial length bounds are placed on the numbers involved (or, equivalently, polynomial time bounds are placed on the Turing machines involved). It gives a finer classification of some sets of natural numbers that are at level of the arithmetical hierarchy.
Read more about this topic: Arithmetical Hierarchy
Famous quotes containing the words relation to, relation and/or machines:
“Any relation to the land, the habit of tilling it, or mining it, or even hunting on it, generates the feeling of patriotism. He who keeps shop on it, or he who merely uses it as a support to his desk and ledger, or to his manufactory, values it less.”
—Ralph Waldo Emerson (1803–1882)
“Any relation to the land, the habit of tilling it, or mining it, or even hunting on it, generates the feeling of patriotism. He who keeps shop on it, or he who merely uses it as a support to his desk and ledger, or to his manufactory, values it less.”
—Ralph Waldo Emerson (1803–1882)
“If men do not keep on speaking terms with children, they cease to be men, and become merely machines for eating and for earning money.”
—John Updike (b. 1932)