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 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.[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

X'=\{x\mid \varphi _{x}^{X}(x)\ {\mbox{is defined}}\}.

The $n$ th Turing jump $X (n)$ is defined inductively by

X^{(0)}=X,

X^{(n+1)}=(X^{(n)})'.

The $ω$ jump $X (ω)$ of $X$ is the effective join of the sequence of sets $X (n)$ for $n \in N$ :

X^{(\omega )}=\{p_{i}^{k}\mid i\in \mathbb {N} {\text{ and }}k\in X^{(i)}\},

where $p i$ denotes the $i$ th prime.

The notation $0'$ or $\emptyset'$ 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.

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.[1] 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).[2]

Examples

The Turing jump $0'$ of the empty set is Turing equivalent to the halting problem.[3]
For each $n$ , the set $0 (n)$ is m-complete at level $\Sigma _{n}^{0}$ 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 (ω)$ .[4]

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.[3]

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

References

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.
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.
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.

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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[:0-1] 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] 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.

[:1-3] 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.

[4] 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.