Post's Theorem and Corollaries
Post's theorem establishes a close connection between the arithmetical hierarchy and the Turing degrees of the form, that is, finitely iterated Turing jumps of the empty set. (The empty set could be replaced with any other computable set without changing the truth of the theorem.)
Post's theorem states:
- A set B is if and only if is recursively enumerable by an oracle Turing machine with an oracle for, that is, if and only if B is .
- The set is complete for every . This means that every set is many-one reducible to .
Post's theorem has many corollaries that expose additional relationships between the arithmetical hierarchy and the Turing degrees. These include:
- Fix a set C. A set B is if and only if B is . This is the relativization of the first part of Post's theorem to the oracle C.
- A set B is if and only if . More generally, B is if and only if .
- A set is defined to be arithmetical if it is for some n. Post's theorem shows that, equivalently, a set is arithmetical if and only if it is Turing reducible to for some m.
Read more about this topic: Post's Theorem
Famous quotes containing the words post and/or theorem:
“I had rather be shut up in a very modest cottage, with my books, my family and a few old friends, dining on simple bacon, and letting the world roll on as it liked, than to occupy the most splendid post which any human power can give.”
—Thomas Jefferson (1743–1826)
“To insure the adoration of a theorem for any length of time, faith is not enough, a police force is needed as well.”
—Albert Camus (1913–1960)