Turing jump

From Wikipedia, the free encyclopedia

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

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 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. 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 $\Sigma _{n}^{0}$ in the arithmetical hierarchy.
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. Check date values in: |date= (help)
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. Retrieved 2008-07-13. Cite uses deprecated parameters (help)
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 available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.