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.^[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.

^ Ambos-Spies, Klaus; Fejer, Peter A. (2014), "Degrees of Unsolvability", Handbook of the History of Logic, vol. 9, Elsevier, pp. 443–494, doi:10.1016/b978-0-444-51624-4.50010-1, ISBN 9780444516244.

[:0-1] Ambos-Spies, Klaus; Fejer, Peter A. (2014), "Degrees of Unsolvability", Handbook of the History of Logic, vol. 9, Elsevier, pp. 443–494, doi:10.1016/b978-0-444-51624-4.50010-1, ISBN 9780444516244.

[1]