Post's theorem

{{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 $\backslash Sigma^\{0\}\_m$ if it is an existential statement in prenex normal form (all quantifiers at the front) with $m$ alternations between existential and universal quantifiers applied to a formula with bounded quantifiers only. Formally a formula $\backslash phi(s)$ in the language of Peano arithmetic is a $\backslash Sigma^\{0\}\_m$ formula if it is of the form

:$\backslash left(\backslash exists\; n^1\_1\backslash exists\; n^1\_2\backslash cdots\backslash exists\; n^1\_\{j\_1\}\backslash right)\backslash left(\backslash forall\; n^2\_1\; \backslash cdots\; \backslash forall\; n^2\_\{j\_2\}\backslash right)\backslash left(\backslash exists\; n^3\_1\backslash cdots\backslash right)\backslash cdots\backslash left(Q\; n^m\_1\; \backslash cdots\; \backslash right)\backslash rho(n^1\_1,\backslash ldots\; n^m\_\{j\_m\},x\_1,\backslash ldots,x\_k)$

where $\backslash rho$ contains only bounded quantifiers and Q is $\backslash forall$ if m is even and $\backslash exists$ if m is odd.

A set of natural numbers $A$ is said to be $\backslash Sigma^0\_m$ if it is definable by a $\backslash Sigma^0\_m$ formula, that is, if there is a $\backslash Sigma^0\_m$ formula $\backslash phi(s)$ such that each number $n$ is in $A$ if and only if $\backslash phi(n)$ holds. It is known that if a set is $\backslash Sigma^0\_m$ then it is $\backslash Sigma^0\_n$ for any $n\; >\; m$, but for each m there is a $\backslash Sigma^0\_\{m+1\}$ set that is not $\backslash 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 arithmetical hierarchy as well as the unrelativized hierarchy just defined. A set $A$ of natural numbers is said to be $\backslash Sigma^0\_m$ relative to a set $B$, written $\backslash Sigma^\{0,B\}\_m$, if $A$ is definable by a $\backslash 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\; \backslash 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\text{'}$ 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^\{(n)\}$ indicates the $n$–fold iterated Turing jump of $A$. Thus $A^\{(0)\}$ is just $A$, and $A^\{(n+1)\}$ is the Turing jump of $A^\{(n)\}$.

Post's theorem establishes a close connection between the arithmetical hierarchy and the Turing degrees of the form $\backslash emptyset^\{(n)\}$, 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:

1. A set $B$ is $\backslash Sigma^0\_\{n+1\}$ if and only if $B$ is recursively enumerable by an oracle Turing machine with an oracle for $\backslash emptyset^\{(n)\}$, that is, if and only if $B$ is $\backslash Sigma^\{0,\backslash emptyset^\{(n)\}\}\_1$.
2. The set $\backslash emptyset^\{(n)\}$ is $\backslash Sigma^0\_n$-complete for every $n\; >\; 0$. This means that every $\backslash Sigma^0\_n$ set is many-one reducible to $\backslash emptyset^\{(n)\}$.

Post's theorem has many corollaries that expose additional relationships between the arithmetical

hierarchy and the Turing degrees. These include:

1. Fix a set $C$. A set $B$ is $\backslash Sigma^\{0,C\}\_\{n+1\}$ if and only if $B$ is $\backslash Sigma^\{0,C^\{(n)\}\}\_1$. This is the relativization of the first part of Post's theorem to the oracle $C$.
2. A set $B$ is $\backslash Delta\_\{n+1\}$ if and only if $B\; \backslash leq\_T\; \backslash emptyset^\{(n)\}$. More generally, $B$ is $\backslash Delta^C\_\{n+1\}$ if and only if $B\; \backslash leq\_T\; C^\{(n)\}$.
3. A set is defined to be arithmetical if it is $\backslash 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 $\backslash emptyset^\{(m)\}$ for some m.

The operation of a Turing machine $T$ on input $n$ can be formalized logically in first-order arithmetic. For example, we may use symbols $A\_k$, $B\_k$, and $C\_k$ for the tape configuration, machine state and location along the tape after $k$ steps, respectively. $T$'s transition system determines the relation between $(A\_k,B\_k,C\_k)$ and $(A\_\{k+1\},B\_\{k+1\},C\_\{k+1\})$; their initial values (for $k=0$) are the input, the initial state and zero, respectively. The machine halts if and only if there is a number $k$ such that $B\_k$ is the halting state.

The exact relation depends on the specific implementation of the notion of Turing machine (e.g. their alphabet, allowed mode of motion along the tape, etc.)

In case $T$ halts at time $n\_1$, the relation between $(A\_k,B\_k,C\_k)$ and $(A\_\{k+1\},B\_\{k+1\},C\_\{k+1\})$ must be satisfied only for k bounded from above by $n\_1$.

Thus there is a formula $\backslash varphi(n,n\_1)$ in first-order arithmetic with no unbounded quantifiers, such that $T$ halts on input $n$ at time $n\_1$ at most if and only if $\backslash varphi(n,n\_1)$ is satisfied.

For example, for a prefix-free Turing machine with binary alphabet and no blank symbol, we may use the following notations:

• $A\_k$ is the 1-ary symbol for the configuration of the whole tape after $k$ steps (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 particular $A\_0$ is the initial configuration of the tape, which corresponds the input to the machine.
• $B\_k$ is the 1-ary symbol for the Turing machine state after $k$ steps. In particular, $B\_0=q\_I$, the initial state of the Turing machine.
• $C\_k$ is the 1-ary symbol for the Turing machine location on the tape after $k$ steps. In particular $C\_0=0$.
• $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 or -1 machine movement along the tape).
• $bit(j,m)$ is the j-th bit of a number $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 $t(n)=\; cat(2^\{ceil(log\_2\; n)\}-1,0,n)$ where cat stands for concatenation; thus $t(n)$ is a $\backslash log(n)-$length string of $1-s$ followed by $0$ and then by $n$.

The operation of the Turing machine at the first $n\_1$ steps can thus be written as the conjunction of the initial conditions and the following formulas, quantified over $k$ for all

• $(B\_\{k+1\},\; bit(C\_k\; ,A\_\{k+1\}),\; D)\; =\; M(B\_k,\; bit(C\_k\; ,A\_k))$. Since M has a finite domain, this can be replaced by a first-order quantifier-free arithmetic formula. The exact formula obviously depends on M.
• $C\_\{k+1\}\; =\; C\_k+D$
• $\backslash forall\; j:\; j\backslash ne\; C\_k\; \backslash rightarrow\; bit(j\; ,A\_\{k+1\})\; =\; bit(j\; ,A\_k)$. Note that at the first $n\_1$ steps, $T$ never arrives at a location along the tape greater than $n\_1$. Thus the universal quantifier over j can be bounded by $n\_1$+1, as bits beyond this location have no relevance for the machine's operation.

T halts on input $n$ at time $n\_1$ at most if and only if $\backslash varphi(n,n\_1)$ is satisfied, where:

:

This is a first-order arithmetic formula with no unbounded quantifiers, i.e. it is in $\backslash Sigma^0\_0$.

Let $S$ be a set that can be recursively enumerated by a Turing machine. Then there is a Turing machine $T$ that for every $n$ in $S$, $T$ halts when given $n$ as an input.

This can be formalized by the first-order arithmetical formula presented above. The members of $S$ are the numbers $n$ satisfying the following formula:

$\backslash exists\; n\_1:\backslash varphi(n,n\_1)$

This formula is in $\backslash Sigma^0\_1$. Therefore, $S$ is in $\backslash Sigma^0\_1$.

Thus every recursively enumerable set is in $\backslash Sigma^0\_1$.

The converse is true as well: for every formula $\backslash varphi(n)$ in $\backslash Sigma^0\_1$ with k existential quantifiers, we may enumerate the $k$–tuples of natural numbers and run a Turing machine that goes through all of them until it finds the formula is satisfied. This Turing machine halts on precisely the set of natural numbers satisfying $\backslash varphi(n)$, and thus enumerates its corresponding set.

Similarly, the operation of an oracle machine $T$ with an oracle O that halts after at most $n\_1$ steps on input $n$ can be described by a first-order formula $\backslash varphi\_O(n,n\_1)$, except that the formula $\backslash varphi\_1(n,n\_1)$ now includes:

• A new predicate, $O\_m$, giving the oracle answer. This predicate must satisfy some formula to be discussed below.
• An additional tape - the oracle tape - on which $T$ has to write the number m for every call O(m) to the oracle; writing on this tape can be logically formalized in a similar manner to writing on the machine's tape. Note that an oracle machine that halts after at most $n\_1$ steps has time to write at most $n\_1$ digits on the oracle tape. So the oracle can only be called with numbers m satisfying .

If the oracle is for a decision problem, $O\_m$ is always "Yes" or "No", which we may formalize as 0 or 1. Suppose the decision problem itself can be formalized by a first-order arithmetic formula $\backslash psi^O(m)$.

Then $T$ halts on $n$ after at most $n\_1$ steps if and only if the following formula is satisfied:

where $\{\backslash varphi\_O\}\_1(n,n\_1)$ is a first-order formula with no unbounded quantifiers.

If O is an oracle to the halting problem of a machine $T\text{'}$, then $\backslash psi^O(m)$ is the same as "there exists $m\_1$ such that $T\text{'}$ starting with input m is at the halting state after $m\_1$ steps".

Thus:

$\backslash psi^O(m)\; =\; \backslash exists\; m\_1:\; \backslash psi\_H(m,m\_1)$

where $\backslash psi\_H(m,m\_1)$ is a first-order formula that formalizes $T\text{'}$. If $T\text{'}$ is a Turing machine (with no oracle), $\backslash psi\_H(m,m\_1)$ is in $\backslash Sigma^0\_0\; =\; \backslash Pi^0\_0$ (i.e. it has no unbounded quantifiers).

Since there is a finite number of numbers m satisfying , we may choose the same number of steps for all of them: there is a number $m\_1$, such that $T\text{'}$ halts after $m\_1$ steps precisely on those inputs for which it halts at all.

Moving to prenex normal form, we get that the oracle machine halts on input $n$ if and only if the following formula is satisfied:

$\backslash varphi(n)\; =\backslash exists\; n\_1\backslash exists\; m\_1\; \backslash forall\; m\_2\; :(\backslash psi\_H(m,m\_2)\backslash rightarrow\; (O\_m=1))\; \backslash land(\backslash lnot\backslash psi\_H(m,m\_1)\backslash rightarrow\; (O\_m=0)))\; \backslash land\; \{\backslash varphi\_O\}\_1(n,n\_1)$

(informally, there is a "maximal number of steps"$m\_1$ such every oracle that does not halt within the first $m\_1$ steps does not stop at all; however, for every$m\_2$, each oracle that halts after $m\_2$ steps does halt).

Note that we may replace both $n\_1$ and $m\_1$ by a single number - their maximum - without changing the truth value of $\backslash varphi(n)$. Thus we may write:

$\backslash varphi(n)\; =\backslash exists\; n\_1\; \backslash forall\; m\_2\; :(\backslash psi\_H(m,m\_2)\backslash rightarrow\; (O\_m=1))\; \backslash land(\backslash lnot\backslash psi\_H(m,n\_1)\backslash rightarrow\; (O\_m=0)))\; \backslash land\; \{\backslash varphi\_O\}\_1(n,n\_1)$

For the oracle to the halting problem over Turing machines, $\backslash psi\_H(m,m\_1)$ is in $\backslash Pi^0\_0$ and $\backslash varphi(n)$ is in $\backslash Sigma^0\_2$. Thus every set that is recursively enumerable by an oracle machine with an oracle for $\backslash emptyset\; ^\{(1)\}$, is in $\backslash Sigma^0\_2$.

The converse is true as well: Suppose $\backslash varphi(n)$ is a formula in $\backslash Sigma^0\_2$ with $k\_1$ existential quantifiers followed by $k\_2$ universal quantifiers. Equivalently, $\backslash varphi(n)$ has $k\_1$> existential quantifiers followed by a negation of a formula in $\backslash Sigma^0\_1$; the latter formula can be enumerated by a Turing machine and can thus be checked immediately by an oracle for $\backslash emptyset\; ^\{(1)\}$.

We may thus enumerate the $k\_1$–tuples of natural numbers and run an oracle machine with an oracle for $\backslash 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 $\backslash varphi(n)$, and thus enumerates its corresponding set.

More generally, suppose every set that is recursively enumerable by an oracle machine with an oracle for $\backslash emptyset\; ^\{(p)\}$ is in $\backslash Sigma^0\_\{p+1\}$. Then for an oracle machine with an oracle for $\backslash emptyset\; ^\{(p+1)\}$, $\backslash psi^O(m)\; =\; \backslash exists\; m\_1:\; \backslash psi\_H(m,m\_1)$ is in $\backslash Sigma^0\_\{p+1\}$.

Since $\backslash psi^O(m)$ is the same as $\backslash varphi(n)$ for the previous Turing jump, it can be constructed (as we have just done with $\backslash varphi(n)$ above) so that $\backslash psi\_H(m,m\_1)$ in $\backslash Pi^0\_p$. After moving to prenex formal form the new $\backslash varphi(n)$ is in $\backslash Sigma^0\_\{p+2\}$.

By induction, every set that is recursively enumerable by an oracle machine with an oracle for $\backslash emptyset\; ^\{(p)\}$, is in $\backslash Sigma^0\_\{p+1\}$.

The other direction can be proven by induction as well: Suppose every formula in $\backslash Sigma^0\_\{p+1\}$ can be enumerated by an oracle machine with an oracle for $\backslash emptyset\; ^\{(p)\}$.

Now Suppose $\backslash varphi(n)$ is a formula in $\backslash Sigma^0\_\{p+2\}$ with $k\_1$ existential quantifiers followed by $k\_2$ universal quantifiers etc. Equivalently, $\backslash varphi(n)$ has $k\_1$> existential quantifiers followed by a negation of a formula in $\backslash Sigma^0\_\{p+1\}$; the latter formula can be enumerated by an oracle machine with an oracle for $\backslash emptyset\; ^\{(p)\}$ and can thus be checked immediately by an oracle for $\backslash emptyset\; ^\{(p+1)\}$.

We may thus enumerate the $k\_1$–tuples of natural numbers and run an oracle machine with an oracle for $\backslash 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 $\backslash varphi(n)$, and thus enumerates its corresponding set.

Rogers, H. The Theory of Recursive Functions and Effective Computability, MIT Press. {{isbn|0-262-68052-1}}; {{isbn|0-07-053522-1}}

Soare, R. Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987. {{isbn|3-540-15299-7}}

Category:Theorems in the foundations of mathematics

Category:Computability theory

Category:Mathematical logic hierarchies