Turing jump
In computability theory, the Turing jump or Turing jump operator, named after 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 that halt when given access to an oracle that solves that problem.
Wikipedia contributors, "Turing jump", Wikipedia, revision 1381255312, retrieved 20 November 2026, source, CC BY-SA 4.0.