Turing jump

The Turing jump of X can be thought of as an oracle to the halting problem for oracle machines with an oracle for X.^[1]

Formally, 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

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

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

$${\displaystyle {\begin{aligned}X^{(0)}&=X,\\X^{(n+1)}&=X^{(n)}{'}.\end{aligned}}}$$

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

$${\displaystyle X^{(\omega )}=\{p_{i}^{k}\mid i\in \mathbb {N} {\text{ and }}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,^[2] and is in particular connected to Post's theorem.

The jump can be iterated into transfinite ordinals: there are jump operators ${\displaystyle j^{\delta }}$ for sets of natural numbers when ${\displaystyle \delta }$ is an ordinal that has a code in Kleene's ${\displaystyle {\mathcal {O}}}$ (regardless of code, the resulting jumps are the same by a theorem of Spector),^[2] in particular the sets 0^(α) for α < ω₁^CK, where ω₁^CK is the Church–Kleene ordinal, are closely related to the hyperarithmetic hierarchy.^[1] Beyond ω₁^CK, the process can be continued through the countable ordinals of the constructible universe, using Jensen's work on fine structure theory of Gödel's L.^[3][2] The concept has also been generalized to extend to uncountable regular cardinals.^[4]

• The Turing jump 0′ of the empty set is Turing equivalent to the halting problem.^[5]
• For each n, the set 0⁽ⁿ⁾ is m-complete at level ${\displaystyle \Sigma _{n}^{0}}$ in the arithmetical hierarchy (by Post's theorem).
• The set of Gödel numbers of true formulas in the language of Peano arithmetic with a predicate for X is computable from X^(ω).^[6]

• 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.^[5]

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