Navigation
  • Home
  • Recent
  • Most Active
  • Popular
  • Blog
  • Credits
  • RSS
    		•
      Interaction
  • Register
  • Statistics
    		•
      Help
  • Suggestions
  • Contact Us
  • How to Edit
  • Help
    		•



    [Edit]


    In computability theory Post's theorem, named after Emil Post, describes the connection between the arithmetical hierarchy and the Turing degrees.
        Post's theorem
            Background
            Posts theorem and corollaries
            Proof of Posts theorem

    top

    Background

    The statement of Post's theorem requires several concepts relating to definability and recursion theory. This section gives a brief overview of these concepts, which are covered in depth in their respective articles.

    The arithmetical hierarchy classifies certain sets of natural numbers that are definable in the language of Peano arithmetic. A formula phi(s) in the language of Peano arithmetic is said to be Sigma^_m if it is of the form
    exists n_1 orall n_2 exists n_3 orall n_4 cdots Q n_m

    ho(s,n_1,ldots,n_m).
    Here Q is orall if m is even and exists if m is odd. A set of natural numbers A is said to be Sigma^0_m if it is definable by a Sigma^0_m formula, that is, if there is a Sigma^0_m formula phi(s) such that each number n is in A if and only if phi(n) holds. It is known that if a set is Sigma^0_m then it is Sigma^0_n for any n > m, but for each m there is a Sigma^0_ set that is not Sigma^0_m. Thus the number of quantifier alternations required to define a set gives a measure of the complexity of the set.

    Post's theorem uses the relativized (also called boldface) arithmetical hierarchy as well as the unrelativized hierarchy just defined. A set A of natural numbers is said to be Sigma^0_m relative to a set B, written Sigma^_m, if
    A is definable by a Sigma^0_m formula in an extended language that includes a predicate for membership in B.

    While the arithmetical hierarchy measures definability of sets of natural numbers, Turing degrees measure the level of uncomputability of sets of natural numbers. A set A is said to be Turing reducible to a set B, written A leq_T B, if there is an oracle Turing machine that, given an oracle for B, computes the characteristic function of A.
    The Turing jump of a set A is a form of the Halting problem relative to A. Given a set A,
    the Turing jump A' is the set of indices of oracle Turing machines that halt on input 0 when run with oracle A. It is known that every set A is Turing reducible to its Turing jump, but the Turing jump of a set is never Turing reducible to the original set.

    Post's theorem uses finitely iterated Turing jumps. For any set A of natural numbers, the notation
    A^ indicates the n-fold iterated Turing jump of A. Thus A^ is just A, and A^ is the Turing jump of A^.

    top

    Posts theorem and corollaries

    Post's theorem establishes a close connection between the arithmetical hierarchy and the Turing degrees of the form emptyset^, 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 Sigma^0_ if and only if B is recursively enumerable by an oracle Turing machine with an oracle for emptyset^, that is, if and only if B is Sigma^_1.
      The set emptyset^ is Sigma^0_n complete for every n > 0. This means that every Sigma^0_n set is many-one reducible to emptyset^.

    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 Sigma^_ if and only if B is Sigma^_1. This is the relativization of the first part of Post's theorem to the oracle C.
      A set B is Delta_ if and only if B leq_T emptyset^. More generally, B is Delta^C_ if and only if B leq_T C^.
      A set is defined to be arithmetical if it is Sigma^0_n for some n. Post's theorem shows that, equivalently, a set is arithmetical if and only if it is Turing reducible to emptyset^ for some m.

    top

    Proof of Posts theorem


     
    Search more:
     

       
    Source Privacy License Download Contact Us Atlas
    Scientus.org Dictionary (Yet Another Wiki) RC : 1.39
    MIT OpenCourseWare
    This article is licensed under the GNU Free Documentation License [copyleft]. It uses material from the Wikipedia article "Post's theorem". link