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. Informally, given a problem, the Turing jump returns the set of Turing machines which halt when given access to an oracle that solves that problem.
Definition
The Turing jump of X can be thought of as an oracle to the halting problem for oracle machines with an oracle to X.
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 nth 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 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.
The jump can be iterated into transfinite ordinals: the sets 0^{(α)} for α < ω_{1}^{CK}, where ω_{1}^{CK} is the Church-Kleene ordinal, are closely related to the hyperarithmetic hierarchy. Beyond ω_{1}^{CK}, the process can be continued through the countable ordinals of the constructible universe, using set-theoretic methods (Hodes 1980). The concept has also been generalized to extend to uncountable regular cardinals (Lubarsky 1987).
Examples
- The Turing jump 0′ of the empty set is Turing equivalent to the halting problem.
- 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^{(ω)}.
Properties
- 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.
Many properties of the Turing jump operator are discussed in the article on Turing degrees.
References
- Ambos-Spies, K. and Fejer, P. Degrees of Unsolvability. Unpublished. http://www.cs.umb.edu/~fejer/articles/History_of_Degrees.pdf
- Hodes, Harold T. (June 1980). "Jumping Through the Transfinite: The Master Code Hierarchy of Turing Degrees". Journal of Symbolic Logic. Association for Symbolic Logic. 45 (2): 204–220. doi:10.2307/2273183. JSTOR 2273183.
- 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. 52 (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.