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.
Definition
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 φiX of the X-computable functions, the Turing jump X′ of X is defined as
- [math]\displaystyle{ X'= \{x \mid \varphi_x^X(x) \ \mbox{is defined} \}. }[/math]
The nth Turing jump X(n) is defined inductively by
- [math]\displaystyle{ X^{(0)} = X, }[/math]
- [math]\displaystyle{ X^{(n+1)} = (X^{(n)})'. }[/math]
The ω jump X(ω) of X is the effective join of the sequence of sets X(n) for n ∈ N:
- [math]\displaystyle{ X^{(\omega)} = \{p_i^k \mid i \in \mathbb{N} \text{ and } k \in X^{(i)}\}, }[/math]
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 [math]\displaystyle{ j^\delta }[/math] for sets of natural numbers when [math]\displaystyle{ \delta }[/math] is an ordinal that has a code in Kleene's [math]\displaystyle{ \mathcal O }[/math] (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]
- For each n, the set 0(n) is m-complete at level [math]\displaystyle{ \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 X is computable from X(ω).[6]
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.[5]
Many properties of the Turing jump operator are discussed in the article on Turing degrees.
References
- ↑ 1.0 1.1 1.2 Ambos-Spies, Klaus; Fejer, Peter A. (2014), "Degrees of Unsolvability", Handbook of the History of Logic (Elsevier) 9: pp. 443–494, doi:10.1016/b978-0-444-51624-4.50010-1, ISBN 9780444516244.
- ↑ 2.0 2.1 2.2 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 (Association for Symbolic Logic) 45 (2): 204–220. doi:10.2307/2273183. https://philarchive.org/rec/HODJTT.
- ↑ 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.
- ↑ 5.0 5.1 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. https://philarchive.org/rec/HODJTT.
- 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 52 (4): pp. 952–958.
- 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". Mathematical Research Letters 6 (5–6): 711–722. doi:10.4310/mrl.1999.v6.n6.a10. http://math.berkeley.edu/~slaman/papers/jump.pdf. 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.
 |  |
