In
computability theory, the Turing jump or Turing jump operator, named for
Alan Turing, is an operation that assigns to each
decision problemX 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.
Formally, given a set X and a
Gödel numberingφiX of the
X-computable functions, the Turing jumpX′ of X is defined as
The nth Turing jumpX(n) is defined inductively by
The ω jumpX(ω) of X is the
effective join of the sequence of sets X(n) for n ∈ N:
where pi denotes the ith prime.
The notation 0′ or ∅′ is often used for the Turing jump of the empty set. It is read zero-jump or sometimes zero-prime.
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.
The jump can be iterated into
transfinite ordinals: there are jump operators for sets of natural numbers when is an ordinal that has a code in Kleene's (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.[4]
Examples
The Turing jump 0′ of the empty set is Turing equivalent to the
halting problem.[5]
Lubarsky, Robert S. (Dec 1987). "Uncountable Master Codes and the Jump Hierarchy". Journal of Symbolic Logic. Vol. 52, no. 4. pp. 952–958.
JSTOR2273829.
Rogers Jr, H. (1987). Theory of recursive functions and effective computability.
MIT Press, Cambridge, MA, USA.
ISBN0-07-053522-1.
Soare, R.I. (1987). Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets. Springer.
ISBN3-540-15299-7.