Turing jump

In computability theory, the Turing jump or Turing jump operator, named for Alan Turing, is an operation that assigns to each decision problem X a successively harder decision problem X ′ with the property that X ′ is not decidable by an oracle machine with an oracle for X.

The operator is called a jump operator because it increases the Turing degree of the problem X. That is, the problem X ′ is not Turing reducible to X. Post's theorem establishes a relationship between the Turing jump operator and the arithmetical hierarchy of sets of natural numbers. Informally, given a problem, the Turing jump returns the set of Turing machines which halt when given access to an oracle that solves that problem.

Definition

Given a set X and a Gödel numbering φ_i^X of the X-computable functions, the Turing jump X ′ of X is defined as

$X'= \{x \mid \varphi_x^X(x) \ \mbox{is defined} \}.$

The nth Turing jump X⁽ⁿ⁾ is defined inductively by

$X^{(0)} = X, \,$

$X^{(n+1)}=(X^{(n)})'. \,$

The ω jump X^(ω) of X is the effective join of the sequence of sets X⁽ⁿ⁾ for n ∈ N:

$X^{(\omega)} = \{p_i^k \mid k \in X^{(i)}\},\,$

where p_i denotes the ith prime.

The notation 0′ or ∅′ is often used for the Turing jump of the empty set. It is read zero-jump or sometimes zero-prime.

Similarly, 0⁽ⁿ⁾ is the nth jump of the empty set. For finite n, these sets are closely related to the arithmetic hierarchy.

The jump can be iterated into transfinite ordinals: the sets 0^(α) for α < ω₁^CK, where ω₁^CK is the Church-Kleene ordinal, are closely related to the hyperarithmetic hierarchy. Beyond ω₁^CK, the process can be continued through the countable ordinals of the constructible universe, using set-theoretic methods (Hodes 1980). The concept has also been generalized to extend to uncountable regular cardinals (Lubarsky 1987).

Examples

• The Turing jump 0′ of the empty set is Turing equivalent to the halting problem.
• For each n, the set 0⁽ⁿ⁾ is m-complete at level $\Sigma^0_n$ in the arithmetical hierarchy.
• The set of Gödel numbers of true formulas in the language of Peano arithmetic with a predicate for X is computable from X^(ω).

Properties

• X ′ is X-computably enumerable but not X-computable.
• If A is Turing equivalent to B then A′ is Turing equivalent to B′. The converse of this implication is not true.
• (Shore and Slaman, 1999) The function mapping X to X ′ is definable in the partial order of the Turing degrees.

Many properties of the Turing jump operator are discussed in the article on Turing degrees.

References

• Ambos-Spies, K. and Fejer, P. Degrees of Unsolvability. Unpublished. http://www.cs.umb.edu/~fejer/articles/History_of_Degrees.pdf