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.

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

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

The $n$ th Turing jump $X (n)$ is defined inductively by

The $ω$ jump $X (ω)$ of $X$ is the effective join of the sequence of sets $X (n)$ for $n \in N$ :

...
Wikipedia