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

Background

The statement of Post's theorem uses several concepts relating to definability and computability 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 first-order Peano arithmetic. A formula if it is an existential statement in prenex normal form alternations between existential and universal quantifiers applied to a formula with bounded quantifiers formula if it is of the form

contains only bounded quantifiers and Q if m if m is odd.

, but for each m. Thus the number of quantifier alternations required to define a set gives a measure of the complexity of the set.

.

While the arithmetical hierarchy measures definability of sets of natural numbers, Turing degrees measure the level of uncomputability is said to be Turing reducible, if there is an oracle Turing machine, computes the characteristic function. The Turing jump is a form of the halting problem is the set of indices 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 and corollaries

, 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. is computably enumerable.

2. set is many-one reducible.

Post's theorem has many corollaries that expose additional relationships between the arithmetical hierarchy and the Turing degrees. These include:

1. .

2. .

3. for some m.

Proof of Post's theorem

Formalization of Turing machines in first-order arithmetic

The operation of a Turing machine can be formalized logically in first-order arithmetic. For example, we may use symbols's transition system 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.)

must be satisfied only for k.

in first-order arithmetic with no unbounded quantifiers 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:

• is the 1-ary symbol steps (which we may write as a number with LSB first, the value of the mth location on the tape being its m is the initial configuration of the tape, which corresponds the input to the machine.

• is the 1-ary, the initial state of the Turing machine.

• is the 1-ary.

• is the transition function of the Turing machine, written as a function from a pair (machine state, bit read by the machine) to a triple (new machine state, bit written by the machine, +1 or -1 machine movement along the tape).

• is the j. 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.

:

• . 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.

• . Thus the universal quantifier over j can be bounded+1, as bits beyond this location have no relevance for the machine's operation.

T is satisfied, where:

.

Computably enumerable sets

be a set that can be computably enumerated by a Turing machine.

satisfying the following formula:

.

with k, and thus enumerates its corresponding set.

Oracle machines

Similarly, the operation of an oracle machine with an oracle O now includes:

• , giving the oracle answer. This predicate must satisfy some formula to be discussed below.

• has to write the number m for every call O(m digits on the oracle tape. So the oracle can only be called with numbers m.

If the oracle is for a decision problem

is a first-order formula with no unbounded quantifiers.

Turing jump

If O starting with input m (i.e. it has no unbounded quantifiers).

Since there is a finite number of numbers m for which it halts at all.

Moving to prenex normal form

steps does halt).

by a single number - their maximum - without changing the truth value

.

.

, and thus enumerates its corresponding set.

Higher Turing jumps

.

.

.

The other direction.

.

, and thus enumerates its corresponding set.

References

Rogers, H. The Theory of Recursive Functions and Effective Computability, MIT Press. ;

Soare, R. Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987.