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:
“There is the falsely mystical view of art that assumes a kind of supernatural inspiration, a possession by universal forces unrelated to questions of power and privilege or the artist’s relation to bread and blood. In this view, the channel of art can only become clogged and misdirected by the artist’s concern with merely temporary and local disturbances. The song is higher than the struggle.”
—Adrienne Rich (b. 1929)
“The adolescent does not develop her identity and individuality by moving outside her family. She is not triggered by some magic unconscious dynamic whereby she rejects her family in favour of her peers or of a larger society.... She continues to develop in relation to her parents. Her mother continues to have more influence over her than either her father or her friends.”
—Terri Apter (20th century)
“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)