# 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 φiX 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(n) is defined inductively by

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

The ω jump X(ω) of X is the effective join of the sequence of sets X(n) for nN:

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

where pi 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(n) 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 α < ω1CK, where ω1CK is the Church-Kleene ordinal, are closely related to the hyperarithmetic hierarchy. Beyond ω1CK, 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).

## Properties

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

## References

|CitationClass=journal }}

• {{#invoke:citation/CS1|citation

|CitationClass=book }}

|CitationClass=book }}

• {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

• {{#invoke:citation/CS1|citation

|CitationClass=book }}