KNOWPIA
WELCOME TO KNOWPIA

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.

The Turing jump of *X* can be thought of as an oracle to the halting problem for oracle machines with an oracle for *X*.^{[1]}

Formally, given a set *X* and a Gödel numbering φ_{i}^{X} of the *X*-computable functions, the **Turing jump** *X*′ of *X* is defined as

The *n*th Turing jump*X*^{(n)} is defined inductively by

The **ω jump** *X*^{(ω)} of *X* is the effective join of the sequence of sets *X*^{(n)} for *n* ∈ **N**:

where *p*_{i} denotes the *i*th 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 *n*th 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 α < ω_{1}^{CK}, where ω_{1}^{CK} is the Church–Kleene ordinal, are closely related to the hyperarithmetic hierarchy.^{[1]} Beyond ω_{1}^{CK}, 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]}

- The Turing jump 0′ of the empty set is Turing equivalent to the halting problem.
^{[5]} - For each
*n*, the set 0^{(n)}is m-complete at level 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
*X*is computable from*X*^{(ω)}.^{[6]}

*X*′ is*X*-computably enumerable but not*X*-computable.- If
*A*is Turing-equivalent to*B*, then*A*′ is Turing-equivalent to*B*′. The converse of this implication is not true. - (Shore and Slaman, 1999) The function mapping
*X*to*X*′ is definable in the partial order of the Turing degrees.^{[5]}

Many properties of the Turing jump operator are discussed in the article on Turing degrees.

- ^
^{a}^{b}^{c}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. - ^
^{a}^{b}^{c}S. G. Simpson, The Hierarchy Based on the Jump Operator, p.269.*The Kleene Symposium*(North-Holland, 1980) **^**Hodes, Harold T. (June 1980). "Jumping Through the Transfinite: The Master Code Hierarchy of Turing Degrees".*Journal of Symbolic Logic*.**45**(2). Association for Symbolic Logic: 204–220. doi:10.2307/2273183. JSTOR 2273183. S2CID 41245500.**^**Lubarsky, Robert S. (December 1987). "Uncountable master codes and the jump hierarchy".*The Journal of Symbolic Logic*.**52**(4): 952–958. doi:10.2307/2273829. ISSN 0022-4812. JSTOR 2273829. S2CID 46113113.- ^
^{a}^{b}Shore, Richard A.; Slaman, Theodore A. (1999). "Defining the Turing Jump".*Mathematical Research Letters*.**6**(6): 711–722. doi:10.4310/MRL.1999.v6.n6.a10. **^**Hodes, Harold T. (June 1980). "Jumping through the transfinite: the master code hierarchy of Turing degrees".*The Journal of Symbolic Logic*.**45**(2): 204–220. doi:10.2307/2273183. ISSN 0022-4812. JSTOR 2273183. S2CID 41245500.

- Ambos-Spies, K. and Fejer, P. Degrees of Unsolvability. Unpublished. http://www.cs.umb.edu/~fejer/articles/History_of_Degrees.pdf
- Lerman, M. (1983).
*Degrees of unsolvability: local and global theory*. Berlin; New York: Springer-Verlag. ISBN 3-540-12155-2. - Lubarsky, Robert S. (Dec 1987). "Uncountable Master Codes and the Jump Hierarchy".
*Journal of Symbolic Logic*. Vol. 52, no. 4. pp. 952–958. JSTOR 2273829. - Rogers Jr, H. (1987).
*Theory of recursive functions and effective computability*. MIT Press, Cambridge, MA, USA. ISBN 0-07-053522-1. - Shore, R.A.; Slaman, T.A. (1999). "Defining the Turing jump" (PDF).
*Mathematical Research Letters*.**6**(5–6): 711–722. doi:10.4310/mrl.1999.v6.n6.a10. Retrieved 2008-07-13. - Soare, R.I. (1987).
*Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets*. Springer. ISBN 3-540-15299-7.