Post's theorem

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

Contenu 1 Arrière plan 2 Post's theorem and corollaries 3 Proof of Post's theorem 3.1 Formalization of Turing machines in first-order arithmetic 3.2 Implementation example 3.3 Recursively enumerable sets 3.4 Oracle machines 3.5 Turing jump 3.6 Higher Turing jumps 4 References Background See also: Arithmetical hierarchy § Relation to Turing machines The statement of Post's theorem uses 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 is said to be {style d'affichage Sigma _{m}^{0}} if it is an existential statement in prenex normal form (all quantifiers at the front) avec {style d'affichage m} alternations between existential and universal quantifiers applied to a formula with bounded quantifiers only. Formally a formula {style d'affichage phi (s)} in the language of Peano arithmetic is a {style d'affichage Sigma _{m}^{0}} formula if it is of the form {style d'affichage à gauche(exists n_{1}^{1}exists n_{2}^{1}cdots exists n_{j_{1}}^{1}droit)la gauche(forall n_{1}^{2}cdots forall n_{j_{2}}^{2}droit)la gauche(exists n_{1}^{3}cdots à droite)cdots left(Qn_{1}^{m}cdots à droite)Rho (n_{1}^{1},ldots n_{j_{m}}^{m},X_{1},ldots ,X_{k})} où {style d'affichage rho } contains only bounded quantifiers and Q is {style d'affichage pour tous } if m is even and {displaystyle exists } if m is odd.

A set of natural numbers {style d'affichage A} is said to be {style d'affichage Sigma _{m}^{0}} if it is definable by a {style d'affichage Sigma _{m}^{0}} formula, C'est, if there is a {style d'affichage Sigma _{m}^{0}} formula {style d'affichage phi (s)} such that each number {displaystyle n} est dans {style d'affichage A} si et seulement si {style d'affichage phi (n)} détient. It is known that if a set is {style d'affichage Sigma _{m}^{0}} then it is {style d'affichage Sigma _{n}^{0}} pour toute {displaystyle n>m} , but for each m there is a {style d'affichage Sigma _{m+1}^{0}} set that is not {style d'affichage Sigma _{m}^{0}} . 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 arithmetical hierarchy as well as the unrelativized hierarchy just defined. A set {style d'affichage A} of natural numbers is said to be {style d'affichage Sigma _{m}^{0}} relative to a set {style d'affichage B} , written {style d'affichage Sigma _{m}^{0,B}} , si {style d'affichage A} is definable by a {style d'affichage Sigma _{m}^{0}} formula in an extended language that includes a predicate for membership in {style d'affichage 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 {style d'affichage A} is said to be Turing reducible to a set {style d'affichage B} , written {displaystyle Aleq _{J}B} , if there is an oracle Turing machine that, given an oracle for {style d'affichage B} , computes the characteristic function of {style d'affichage A} . The Turing jump of a set {style d'affichage A} is a form of the Halting problem relative to {style d'affichage A} . Given a set {style d'affichage A} , the Turing jump {style d'affichage A'} is the set of indices of oracle Turing machines that halt on input {style d'affichage 0} when run with oracle {style d'affichage A} . It is known that every set {style d'affichage 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 {style d'affichage A} of natural numbers, the notation {style d'affichage A^{(n)}} indicates the {displaystyle n} –fold iterated Turing jump of {style d'affichage A} . Ainsi {style d'affichage A^{(0)}} est juste {style d'affichage A} , et {style d'affichage A^{(n+1)}} is the Turing jump of {style d'affichage A^{(n)}} .

Post's theorem and corollaries Post's theorem establishes a close connection between the arithmetical hierarchy and the Turing degrees of the form {displaystyle emptyset ^{(n)}} , C'est, 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 {style d'affichage B} est {style d'affichage Sigma _{n+1}^{0}} si et seulement si {style d'affichage B} is recursively enumerable by an oracle Turing machine with an oracle for {displaystyle emptyset ^{(n)}} , C'est, si et seulement si {style d'affichage B} est {style d'affichage Sigma _{1}^{0,emptyset ^{(n)}}} . The set {displaystyle emptyset ^{(n)}} est {style d'affichage Sigma _{n}^{0}} -complete for every {displaystyle n>0} . This means that every {style d'affichage Sigma _{n}^{0}} set is many-one reducible to {displaystyle emptyset ^{(n)}} .

Post's theorem has many corollaries that expose additional relationships between the arithmetical hierarchy and the Turing degrees. These include: Fix a set {displaystyle C} . A set {style d'affichage B} est {style d'affichage Sigma _{n+1}^{0,C}} si et seulement si {style d'affichage B} est {style d'affichage Sigma _{1}^{0,C^{(n)}}} . This is the relativization of the first part of Post's theorem to the oracle {displaystyle C} . A set {style d'affichage B} est {style d'affichage Delta _{n+1}} si et seulement si {displaystyle Bleq _{J}emptyset ^{(n)}} . Plus généralement, {style d'affichage B} est {style d'affichage Delta _{n+1}^{C}} si et seulement si {displaystyle Bleq _{J}C^{(n)}} . A set is defined to be arithmetical if it is {style d'affichage Sigma _{n}^{0}} pour certains {displaystyle n} . Post's theorem shows that, de manière équivalente, a set is arithmetical if and only if it is Turing reducible to {displaystyle emptyset ^{(m)}} for some m. Proof of Post's theorem Formalization of Turing machines in first-order arithmetic The operation of a Turing machine {style d'affichage T} on input {displaystyle n} can be formalized logically in first-order arithmetic. Par exemple, we may use symbols {style d'affichage A_{k}} , {style d'affichage B_{k}} , et {displaystyle C_{k}} for the tape configuration, machine state and location along the tape after {style d'affichage k} pas, respectivement. {style d'affichage T} 's transition system determines the relation between {style d'affichage (UN_{k},B_{k},C_{k})} et {style d'affichage (UN_{k+1},B_{k+1},C_{k+1})} ; their initial values (pour {displaystyle k=0} ) are the input, the initial state and zero, respectivement. The machine halts if and only if there is a number {style d'affichage k} tel que {style d'affichage B_{k}} is the halting state.

The exact relation depends on the specific implementation of the notion of Turing machine (par exemple. their alphabet, allowed mode of motion along the tape, etc.) In case {style d'affichage T} halts at time {displaystyle n_{1}} , the relation between {style d'affichage (UN_{k},B_{k},C_{k})} et {style d'affichage (UN_{k+1},B_{k+1},C_{k+1})} must be satisfied only for k bounded from above by {displaystyle n_{1}} .

Thus there is a formula {style d'affichage varphi (n,n_{1})} in first-order arithmetic with no unbounded quantifiers, tel que {style d'affichage T} halts on input {displaystyle n} au moment {displaystyle n_{1}} at most if and only if {style d'affichage varphi (n,n_{1})} is satisfied.

Implementation example For example, for a prefix-free Turing machine with binary alphabet and no blank symbol, we may use the following notations: {style d'affichage A_{k}} is the 1-ary symbol for the configuration of the whole tape after {style d'affichage k} pas (which we may write as a number with LSB first, the value of the m-th location on the tape being its m-th least significant bit). En particulier {style d'affichage A_{0}} is the initial configuration of the tape, which corresponds the input to the machine. {style d'affichage B_{k}} is the 1-ary symbol for the Turing machine state after {style d'affichage k} pas. En particulier, {style d'affichage B_{0}=q_{je}} , the initial state of the Turing machine. {displaystyle C_{k}} is the 1-ary symbol for the Turing machine location on the tape after {style d'affichage k} pas. En particulier {displaystyle C_{0}=0} . {style d'affichage M(q,b)} is the transition function of the Turing machine, written as a function from a doublet (machine state, bit read by the machine) to a triplet (new machine state, bit written by the machine, +1 ou -1 machine movement along the tape). {displaystyle bit(j,m)} is the j-th bit of a number {style d'affichage m} . This can be written as a first-order arithmetic formula with no unbounded quantifiers.

For a prefix-free Turing machine we may use, for input n, the initial tape configuration {style d'affichage t(n)=cat(2^{plafond(log_{2}n)}-1,0,n)} where cat stands for concatenation; Donc {style d'affichage t(n)} est un {displaystyle log(n)-} length string of {displaystyle 1-s} followed by {style d'affichage 0} and then by {displaystyle n} .

The operation of the Turing machine at the first {displaystyle n_{1}} steps can thus be written as the conjunction of the initial conditions and the following formulas, quantified over {style d'affichage k} pour tous {style d'affichage k existential quantifiers followed by a negation of a formula in {style d'affichage Sigma _{1}^{0}} ; the latter formula can be enumerated by a Turing machine and can thus be checked immediately by an oracle for {displaystyle emptyset ^{(1)}} .

We may thus enumerate the {style d'affichage k_{1}} –tuples of natural numbers and run an oracle machine with an oracle for {displaystyle emptyset ^{(1)}} that goes through all of them until it finds a satisfaction for the formula. This oracle machine halts on precisely the set of natural numbers satisfying {style d'affichage varphi (n)} , and thus enumerates its corresponding set.

Higher Turing jumps More generally, suppose every set that is recursively enumerable by an oracle machine with an oracle for {displaystyle emptyset ^{(p)}} est dans {style d'affichage Sigma _{p+1}^{0}} . Then for an oracle machine with an oracle for {displaystyle emptyset ^{(p+1)}} , {displaystyle psi ^{O}(m)=exists m_{1}:psi _{H}(m,m_{1})} est dans {style d'affichage Sigma _{p+1}^{0}} .

Depuis {displaystyle psi ^{O}(m)} is the same as {style d'affichage varphi (n)} for the previous Turing jump, it can be constructed (as we have just done with {style d'affichage varphi (n)} au dessus) pour que {style d'affichage psi _{H}(m,m_{1})} dans {displaystyle Pi _{p}^{0}} . After moving to prenex formal form the new {style d'affichage varphi (n)} est dans {style d'affichage Sigma _{p+2}^{0}} .

Par induction, every set that is recursively enumerable by an oracle machine with an oracle for {displaystyle emptyset ^{(p)}} , est dans {style d'affichage Sigma _{p+1}^{0}} .

The other direction can be proven by induction as well: Suppose every formula in {style d'affichage Sigma _{p+1}^{0}} can be enumerated by an oracle machine with an oracle for {displaystyle emptyset ^{(p)}} .

Now Suppose {style d'affichage varphi (n)} is a formula in {style d'affichage Sigma _{p+2}^{0}} avec {style d'affichage k_{1}} existential quantifiers followed by {style d'affichage k_{2}} universal quantifiers etc. De manière équivalente, {style d'affichage varphi (n)} a {style d'affichage k_{1}} > existential quantifiers followed by a negation of a formula in {style d'affichage Sigma _{p+1}^{0}} ; the latter formula can be enumerated by an oracle machine with an oracle for {displaystyle emptyset ^{(p)}} and can thus be checked immediately by an oracle for {displaystyle emptyset ^{(p+1)}} .

We may thus enumerate the {style d'affichage k_{1}} –tuples of natural numbers and run an oracle machine with an oracle for {displaystyle emptyset ^{(p+1)}} that goes through all of them until it finds a satisfaction for the formula. This oracle machine halts on precisely the set of natural numbers satisfying {style d'affichage varphi (n)} , and thus enumerates its corresponding set.

References Rogers, H. La théorie des fonctions récursives et la calculabilité effective, Presse du MIT. ISBN 0-262-68052-1; ISBN 0-07-053522-1 Soleil, R. Ensembles et degrés récursivement énumérables. Perspectives en logique mathématique. Springer Verlag, Berlin, 1987. ISBN 3-540-15299-7 Catégories: Theorems in the foundations of mathematicsComputability theoryMathematical logic hierarchies