In computability theory, the Turing jump or Turing jump operator, named for Alan Turing, is an operation that assigns to each decision problem a successively harder decision problem with the property that is not decidable by an oracle machine with an oracle for .
The operator is called a jump operator because it increases the Turing degree of the problem . That is, the problem is not Turing-reducible to . 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.
Definition
The Turing jump of can be thought of as an oracle to the halting problem for oracle machines with an oracle for . and is in particular connected to Post's theorem.
The jump can be iterated into transfinite ordinals: there are jump operators <math>j^\delta</math> for sets of natural numbers when <math>\delta</math> is an ordinal that has a code in Kleene's <math>\mathcal O</math> (regardless of code, the resulting jumps are the same by a theorem of Spector),
Examples
- The Turing jump of the empty set is Turing equivalent to the halting problem.
- For each , the set is m-complete at level <math>\Sigma^0_n</math> in the arithmetical hierarchy (by Post's theorem).
- The set of Gödel numbers of true formulas in the language of Peano arithmetic with a predicate for is computable from .
Properties
- is -computably enumerable but not -computable.
- If is Turing-equivalent to , then is Turing-equivalent to . The converse of this implication is not true.
- (Shore and Slaman, 1999) The function mapping to is definable in the partial order of the Turing degrees.