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:
“We must get back into relation, vivid and nourishing relation to the cosmos and the universe. The way is through daily ritual, and is an affair of the individual and the household, a ritual of dawn and noon and sunset, the ritual of the kindling fire and pouring water, the ritual of the first breath, and the last.”
—D.H. (David Herbert)
“The instincts of the ant are very unimportant, considered as the ant’s; but the moment a ray of relation is seen to extend from it to man, and the little drudge is seen to be a monitor, a little body with a mighty heart, then all its habits, even that said to be recently observed, that it never sleeps, become sublime.”
—Ralph Waldo Emerson (1803–1882)
“There are bills to be paid, machines to keep in repair,
Irregular verbs to learn, the Time Being to redeem
From insignificance.”
—W.H. (Wystan Hugh)