---
tag: 841C9J1QTC
kind: definition
name: Turing jump
msc: [03D28, 03D30]
defines: 60P2XWY5QX
uses: [Z5CCVBME2V, PA4PYQ1PZ0, P5N2ND3VCG]
sources:
  - url: https://en.wikipedia.org/wiki/Turing_jump
---

## Definition

Let $M_0, M_1, \ldots$ be a fixed effective list of all [[oracle machines|Z5CCVBME2V]].
Let $A \subseteq \N$.
The *Turing jump* of $A$ is the set
$$A' = \set{e \in \N : M_e^A \text{ halts on input } e}.$$
The $n$-th jump $A^{(n)}$ is defined by $A^{(0)} = A$ and $A^{(n+1)} = (A^{(n)})'$.
For a [[Turing degree|P5N2ND3VCG]] $\mathbf{a} = \deg(A)$, the jump is $\mathbf{a}' = \deg(A')$.

## Remarks

Example: for $A = \emptyset$, the machine $M_e^{\emptyset}$ never gets a "yes" answer, so it behaves like an ordinary Turing machine.
Hence $\emptyset'$ is the set $\set{e : M_e \text{ halts on input } e}$, a form of the [[halting problem|Z7TN2B35B0]].

The definition of $\mathbf{a}'$ is legitimate: if $A \le_T B$, then $A' \le_T B'$, so $A \equiv_T B$ implies $A' \equiv_T B'$.
For every $A$, one has $A <_T A'$, that is, $A \le_T A'$ and $A' \not\le_T A$; the proof is a diagonal argument as for the halting problem.
The jump of $A$ does depend on the chosen list of machines, but only up to a computable permutation, so its degree does not.
By [[Post's theorem|NYJX5QXX1T]], $\emptyset^{(n)}$ is complete for the $\Sigma^0_n$ sets of the [[arithmetical hierarchy|7CVJCQKY41]] for $n \ge 1$.