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.
Post's theorem establishes a relationship between the Turing jump operator and the arithmetical hierarchy of sets of natural numbers.
[1] Informally, given a problem, the Turing jump returns the set of Turing machines that halt when given access to an oracle that solves that problem.
[1] Formally, given a set X and a Gödel numbering φiX of the X-computable functions, the Turing jump X′ of X is defined as
The nth Turing jump X(n) is defined inductively by
The notation 0′ or ∅′ is often used for the Turing jump of the empty set.
Similarly, 0(n) 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.
(regardless of code, the resulting jumps are the same by a theorem of Spector),[2] in particular the sets 0(α) for α < ω1CK, where ω1CK is the Church–Kleene ordinal, are closely related to the hyperarithmetic hierarchy.
[1] Beyond ω1CK, 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.