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.

Conteúdo 1 Fundo 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 {estilo de exibição Sigma _{m}^{0}} if it is an existential statement in prenex normal form (all quantifiers at the front) com {estilo de exibição m} alternations between existential and universal quantifiers applied to a formula with bounded quantifiers only. Formally a formula {estilo de exibição phi (s)} in the language of Peano arithmetic is a {estilo de exibição Sigma _{m}^{0}} formula if it is of the form {estilo de exibição à esquerda(exists n_{1}^{1}exists n_{2}^{1}cdots exists n_{j_{1}}^{1}certo)deixei(forall n_{1}^{2}cdots forall n_{j_{2}}^{2}certo)deixei(exists n_{1}^{3}cdots certo)cdots left(Qn_{1}^{m}cdots certo)rho (n_{1}^{1},ldots n_{j_{m}}^{m},x_{1},ldots ,x_{k})} Onde {estilo de exibição rho } contains only bounded quantifiers and Q is {displaystyle forall } if m is even and {displaystyle exists } if m is odd.

A set of natural numbers {estilo de exibição A} is said to be {estilo de exibição Sigma _{m}^{0}} if it is definable by a {estilo de exibição Sigma _{m}^{0}} formula, isso é, if there is a {estilo de exibição Sigma _{m}^{0}} formula {estilo de exibição phi (s)} such that each number {estilo de exibição m} é em {estilo de exibição A} se e apenas se {estilo de exibição phi (n)} detém. It is known that if a set is {estilo de exibição Sigma _{m}^{0}} then it is {estilo de exibição Sigma _{n}^{0}} para qualquer {displaystyle n>m} , but for each m there is a {estilo de exibição Sigma _{m+1}^{0}} set that is not {estilo de exibição 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 {estilo de exibição A} of natural numbers is said to be {estilo de exibição Sigma _{m}^{0}} relative to a set {estilo de exibição B} , written {estilo de exibição Sigma _{m}^{0,B}} , E se {estilo de exibição A} is definable by a {estilo de exibição Sigma _{m}^{0}} formula in an extended language that includes a predicate for membership in {estilo de exibição 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 {estilo de exibição A} is said to be Turing reducible to a set {estilo de exibição B} , written {displaystyle Aleq _{T}B} , if there is an oracle Turing machine that, given an oracle for {estilo de exibição B} , computes the characteristic function of {estilo de exibição A} . The Turing jump of a set {estilo de exibição A} is a form of the Halting problem relative to {estilo de exibição A} . Given a set {estilo de exibição A} , the Turing jump {estilo de exibição A'} is the set of indices of oracle Turing machines that halt on input {estilo de exibição 0} when run with oracle {estilo de exibição A} . It is known that every set {estilo de exibição 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 {estilo de exibição A} of natural numbers, the notation {estilo de exibição A^{(n)}} indicates the {estilo de exibição m} –fold iterated Turing jump of {estilo de exibição A} . Desta forma {estilo de exibição A^{(0)}} é apenas {estilo de exibição A} , e {estilo de exibição A^{(n+1)}} is the Turing jump of {estilo de exibição 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)}} , isso é, 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 {estilo de exibição B} é {estilo de exibição Sigma _{n+1}^{0}} se e apenas se {estilo de exibição B} is recursively enumerable by an oracle Turing machine with an oracle for {displaystyle emptyset ^{(n)}} , isso é, se e apenas se {estilo de exibição B} é {estilo de exibição Sigma _{1}^{0,emptyset ^{(n)}}} . The set {displaystyle emptyset ^{(n)}} é {estilo de exibição Sigma _{n}^{0}} -complete for every {displaystyle n>0} . This means that every {estilo de exibição 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 {estilo de exibição C} . A set {estilo de exibição B} é {estilo de exibição Sigma _{n+1}^{0,C}} se e apenas se {estilo de exibição B} é {estilo de exibição Sigma _{1}^{0,C^{(n)}}} . This is the relativization of the first part of Post's theorem to the oracle {estilo de exibição C} . A set {estilo de exibição B} é {estilo de exibição Delta _{n+1}} se e apenas se {displaystyle Bleq _{T}emptyset ^{(n)}} . De forma geral, {estilo de exibição B} é {estilo de exibição Delta _{n+1}^{C}} se e apenas se {displaystyle Bleq _{T}C^{(n)}} . A set is defined to be arithmetical if it is {estilo de exibição Sigma _{n}^{0}} para alguns {estilo de exibição m} . Post's theorem shows that, equivalentemente, 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 {estilo de exibição T} on input {estilo de exibição m} can be formalized logically in first-order arithmetic. Por exemplo, we may use symbols {estilo de exibição A_{k}} , {estilo de exibição B_{k}} , e {estilo de exibição C_{k}} for the tape configuration, machine state and location along the tape after {estilo de exibição k} degraus, respectivamente. {estilo de exibição T} 's transition system determines the relation between {estilo de exibição (UMA_{k},B_{k},C_{k})} e {estilo de exibição (UMA_{k+1},B_{k+1},C_{k+1})} ; their initial values (por {displaystyle k=0} ) are the input, the initial state and zero, respectivamente. The machine halts if and only if there is a number {estilo de exibição k} de tal modo que {estilo de exibição B_{k}} is the halting state.

The exact relation depends on the specific implementation of the notion of Turing machine (por exemplo. their alphabet, allowed mode of motion along the tape, etc.) In case {estilo de exibição T} halts at time {estilo de exibição n_{1}} , the relation between {estilo de exibição (UMA_{k},B_{k},C_{k})} e {estilo de exibição (UMA_{k+1},B_{k+1},C_{k+1})} must be satisfied only for k bounded from above by {estilo de exibição n_{1}} .

Thus there is a formula {estilo de exibição varphi (n,n_{1})} in first-order arithmetic with no unbounded quantifiers, de tal modo que {estilo de exibição T} halts on input {estilo de exibição m} at time {estilo de exibição n_{1}} at most if and only if {estilo de exibição 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: {estilo de exibição A_{k}} is the 1-ary symbol for the configuration of the whole tape after {estilo de exibição k} degraus (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). Em particular {estilo de exibição A_{0}} is the initial configuration of the tape, which corresponds the input to the machine. {estilo de exibição B_{k}} is the 1-ary symbol for the Turing machine state after {estilo de exibição k} degraus. Em particular, {estilo de exibição B_{0}=q_{EU}} , the initial state of the Turing machine. {estilo de exibição C_{k}} is the 1-ary symbol for the Turing machine location on the tape after {estilo de exibição k} degraus. Em particular {estilo de exibição C_{0}=0} . {estilo de exibição 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 {estilo de exibição 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 {estilo de exibição t(n)=cat(2^{teto(log_{2}n)}-1,0,n)} where cat stands for concatenation; portanto {estilo de exibição t(n)} é um {displaystyle log(n)-} length string of {displaystyle 1-s} Seguido por {estilo de exibição 0} and then by {estilo de exibição m} .

The operation of the Turing machine at the first {estilo de exibição n_{1}} steps can thus be written as the conjunction of the initial conditions and the following formulas, quantified over {estilo de exibição k} para todos {estilo de exibição k existential quantifiers followed by a negation of a formula in {estilo de exibição 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 {estilo de exibição 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 {estilo de exibição 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)}} é em {estilo de exibição 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})} é em {estilo de exibição Sigma _{p+1}^{0}} .

Desde {displaystyle psi ^{O}(m)} is the same as {estilo de exibição varphi (n)} for the previous Turing jump, it can be constructed (as we have just done with {estilo de exibição varphi (n)} acima de) de modo a {estilo de exibição psi _{H}(m,m_{1})} dentro {displaystyle Pi _{p}^{0}} . After moving to prenex formal form the new {estilo de exibição varphi (n)} é em {estilo de exibição Sigma _{p+2}^{0}} .

Por indução, every set that is recursively enumerable by an oracle machine with an oracle for {displaystyle emptyset ^{(p)}} , é em {estilo de exibição Sigma _{p+1}^{0}} .

The other direction can be proven by induction as well: Suppose every formula in {estilo de exibição Sigma _{p+1}^{0}} can be enumerated by an oracle machine with an oracle for {displaystyle emptyset ^{(p)}} .

Now Suppose {estilo de exibição varphi (n)} is a formula in {estilo de exibição Sigma _{p+2}^{0}} com {estilo de exibição k_{1}} existential quantifiers followed by {estilo de exibição k_{2}} universal quantifiers etc. Equivalentemente, {estilo de exibição varphi (n)} tem {estilo de exibição k_{1}} > existential quantifiers followed by a negation of a formula in {estilo de exibição 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 {estilo de exibição 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 {estilo de exibição varphi (n)} , and thus enumerates its corresponding set.

References Rogers, H. A Teoria das Funções Recursivas e Computabilidade Eficaz, Imprensa do MIT. ISBN 0-262-68052-1; ISBN 0-07-053522-1 Sol, R. Conjuntos e graus recursivamente enumeráveis. Perspectivas em Lógica Matemática. Springer-Verlag, Berlim, 1987. ISBN 3-540-15299-7 Categorias: Theorems in the foundations of mathematicsComputability theoryMathematical logic hierarchies