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.
Contenuti 1 Sfondo 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 {displaystyle Sigma _{m}^{0}} if it is an existential statement in prenex normal form (all quantifiers at the front) insieme a {stile di visualizzazione m} alternations between existential and universal quantifiers applied to a formula with bounded quantifiers only. Formally a formula {stile di visualizzazione phi (S)} in the language of Peano arithmetic is a {displaystyle Sigma _{m}^{0}} formula if it is of the form {stile di visualizzazione a sinistra(exists n_{1}^{1}exists n_{2}^{1}cdots exists n_{j_{1}}^{1}Giusto)sinistra(forall n_{1}^{2}cdots forall n_{j_{2}}^{2}Giusto)sinistra(exists n_{1}^{3}cdot a destra)cdots left(Qn_{1}^{m}cdot a destra)rho (n_{1}^{1},ldots n_{j_{m}}^{m},X_{1},ldot ,X_{K})} dove {stile di visualizzazione 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 {stile di visualizzazione A} is said to be {displaystyle Sigma _{m}^{0}} if it is definable by a {displaystyle Sigma _{m}^{0}} formula, questo è, if there is a {displaystyle Sigma _{m}^{0}} formula {stile di visualizzazione phi (S)} such that each number {stile di visualizzazione n} è dentro {stile di visualizzazione A} se e solo se {stile di visualizzazione phi (n)} tiene. It is known that if a set is {displaystyle Sigma _{m}^{0}} then it is {displaystyle Sigma _{n}^{0}} per ogni {displaystyle n>m} , but for each m there is a {displaystyle Sigma _{m+1}^{0}} set that is not {displaystyle 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 {stile di visualizzazione A} of natural numbers is said to be {displaystyle Sigma _{m}^{0}} relative to a set {stile di visualizzazione B} , written {displaystyle Sigma _{m}^{0,B}} , Se {stile di visualizzazione A} is definable by a {displaystyle Sigma _{m}^{0}} formula in an extended language that includes a predicate for membership in {stile di visualizzazione 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 {stile di visualizzazione A} is said to be Turing reducible to a set {stile di visualizzazione B} , written {displaystyle Aleq _{T}B} , if there is an oracle Turing machine that, given an oracle for {stile di visualizzazione B} , computes the characteristic function of {stile di visualizzazione A} . The Turing jump of a set {stile di visualizzazione A} is a form of the Halting problem relative to {stile di visualizzazione A} . Given a set {stile di visualizzazione A} , the Turing jump {stile di visualizzazione A'} is the set of indices of oracle Turing machines that halt on input {stile di visualizzazione 0} when run with oracle {stile di visualizzazione A} . It is known that every set {stile di visualizzazione 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 {stile di visualizzazione A} of natural numbers, the notation {stile di visualizzazione A^{(n)}} indicates the {stile di visualizzazione n} –fold iterated Turing jump of {stile di visualizzazione A} . così {stile di visualizzazione A^{(0)}} è solo {stile di visualizzazione A} , e {stile di visualizzazione A^{(n+1)}} is the Turing jump of {stile di visualizzazione 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)}} , questo è, 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 {stile di visualizzazione B} è {displaystyle Sigma _{n+1}^{0}} se e solo se {stile di visualizzazione B} is recursively enumerable by an oracle Turing machine with an oracle for {displaystyle emptyset ^{(n)}} , questo è, se e solo se {stile di visualizzazione B} è {displaystyle Sigma _{1}^{0,emptyset ^{(n)}}} . Il set {displaystyle emptyset ^{(n)}} è {displaystyle Sigma _{n}^{0}} -complete for every {displaystyle n>0} . This means that every {displaystyle 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 {stile di visualizzazione C} . A set {stile di visualizzazione B} è {displaystyle Sigma _{n+1}^{0,C}} se e solo se {stile di visualizzazione B} è {displaystyle Sigma _{1}^{0,C^{(n)}}} . This is the relativization of the first part of Post's theorem to the oracle {stile di visualizzazione C} . A set {stile di visualizzazione B} è {stile di visualizzazione Delta _{n+1}} se e solo se {displaystyle Bleq _{T}emptyset ^{(n)}} . Più generalmente, {stile di visualizzazione B} è {stile di visualizzazione Delta _{n+1}^{C}} se e solo se {displaystyle Bleq _{T}C^{(n)}} . A set is defined to be arithmetical if it is {displaystyle Sigma _{n}^{0}} per alcuni {stile di visualizzazione n} . 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 {stile di visualizzazione T} on input {stile di visualizzazione n} can be formalized logically in first-order arithmetic. Per esempio, we may use symbols {stile di visualizzazione A_{K}} , {stile di visualizzazione B_{K}} , e {stile di visualizzazione C_{K}} for the tape configuration, machine state and location along the tape after {stile di visualizzazione k} passi, rispettivamente. {stile di visualizzazione T} 's transition system determines the relation between {stile di visualizzazione (UN_{K},B_{K},C_{K})} e {stile di visualizzazione (UN_{k+1},B_{k+1},C_{k+1})} ; their initial values (per {displaystyle k=0} ) are the input, the initial state and zero, rispettivamente. The machine halts if and only if there is a number {stile di visualizzazione k} tale che {stile di visualizzazione B_{K}} is the halting state.
The exact relation depends on the specific implementation of the notion of Turing machine (per esempio. their alphabet, allowed mode of motion along the tape, eccetera.) In case {stile di visualizzazione T} halts at time {stile di visualizzazione n_{1}} , the relation between {stile di visualizzazione (UN_{K},B_{K},C_{K})} e {stile di visualizzazione (UN_{k+1},B_{k+1},C_{k+1})} must be satisfied only for k bounded from above by {stile di visualizzazione n_{1}} .
Thus there is a formula {stile di visualizzazione varphi (n,n_{1})} in first-order arithmetic with no unbounded quantifiers, tale che {stile di visualizzazione T} halts on input {stile di visualizzazione n} a tempo {stile di visualizzazione n_{1}} at most if and only if {stile di visualizzazione 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: {stile di visualizzazione A_{K}} is the 1-ary symbol for the configuration of the whole tape after {stile di visualizzazione k} passi (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). In particolare {stile di visualizzazione A_{0}} is the initial configuration of the tape, which corresponds the input to the machine. {stile di visualizzazione B_{K}} is the 1-ary symbol for the Turing machine state after {stile di visualizzazione k} passi. In particolare, {stile di visualizzazione B_{0}=q_{io}} , the initial state of the Turing machine. {stile di visualizzazione C_{K}} is the 1-ary symbol for the Turing machine location on the tape after {stile di visualizzazione k} passi. In particolare {stile di visualizzazione C_{0}=0} . {stile di visualizzazione 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 o -1 machine movement along the tape). {displaystyle bit(j,m)} is the j-th bit of a number {stile di visualizzazione 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 {stile di visualizzazione t(n)=cat(2^{soffitto(log_{2}n)}-1,0,n)} where cat stands for concatenation; così {stile di visualizzazione t(n)} è un {registro dello stile di visualizzazione(n)-} length string of {displaystyle 1-s} followed by {stile di visualizzazione 0} and then by {stile di visualizzazione n} .
The operation of the Turing machine at the first {stile di visualizzazione n_{1}} steps can thus be written as the conjunction of the initial conditions and the following formulas, quantified over {stile di visualizzazione k} per tutti {stile di visualizzazione k
We may thus enumerate the {stile di visualizzazione 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 {stile di visualizzazione 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)}} è dentro {displaystyle 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})} è dentro {displaystyle Sigma _{p+1}^{0}} .
Da {displaystyle psi ^{o}(m)} is the same as {stile di visualizzazione varphi (n)} for the previous Turing jump, it can be constructed (as we have just done with {stile di visualizzazione varphi (n)} sopra) affinché {stile di visualizzazione psi _{H}(m,m_{1})} in {displaystyle Pi _{p}^{0}} . After moving to prenex formal form the new {stile di visualizzazione varphi (n)} è dentro {displaystyle Sigma _{p+2}^{0}} .
Per induzione, every set that is recursively enumerable by an oracle machine with an oracle for {displaystyle emptyset ^{(p)}} , è dentro {displaystyle Sigma _{p+1}^{0}} .
The other direction can be proven by induction as well: Suppose every formula in {displaystyle Sigma _{p+1}^{0}} can be enumerated by an oracle machine with an oracle for {displaystyle emptyset ^{(p)}} .
Now Suppose {stile di visualizzazione varphi (n)} is a formula in {displaystyle Sigma _{p+2}^{0}} insieme a {stile di visualizzazione k_{1}} existential quantifiers followed by {stile di visualizzazione k_{2}} universal quantifiers etc. Equivalentemente, {stile di visualizzazione varphi (n)} ha {stile di visualizzazione k_{1}} > existential quantifiers followed by a negation of a formula in {displaystyle 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 {stile di visualizzazione 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 {stile di visualizzazione varphi (n)} , and thus enumerates its corresponding set.
References Rogers, H. La teoria delle funzioni ricorsive e della computabilità effettiva, MIT stampa. ISBN 0-262-68052-1; ISBN 0-07-053522-1 Sole, R. Insiemi e gradi ricorsivamente enumerabili. Prospettive in logica matematica. Springer-Verlag, Berlino, 1987. ISBN 3-540-15299-7 Categorie: Theorems in the foundations of mathematicsComputability theoryMathematical logic hierarchies
Se vuoi conoscere altri articoli simili a Post's theorem puoi visitare la categoria Computability theory.
lascia un commento