Turing jump

In computability theory, the Turing jump or Turing jump operator, named for Alan Turing, is intuitively described as 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.

Definition

Given a set "X" and a Gödel numbering $varphi\_i^X$ of the "X"-computable functions, the Turing jump "X"′ of "X" is defined as

:$X\text{'}=\; \{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)\})\text{'}.\; ,$

The ω jump "X"^(ω) of "X" is the effective join of the sequence of sets $langle\; X^\{(n)\}mid\; n\; in\; mathbb\{N\}\; angle$:

:$X^\{(omega)\}\; =\; \{p\_i^k\; mid\; k\; in\; X^\{(i)\}\},,$

where $p\_i$ denotes the "i"th prime.

The notation 0′ is often used for the Turing jump of the empty set, which can also be written as

:$emptyset\text{'}.$

Similarly, $0^\{(n)\}$ is the "n"th jump of the empty set.

Examples

* The Turing jump $varnothing\text{'}$ of the empty set is Turing equivalent to the halting problem.
* For each "n", the set $varnothing^\{(n)\}$ is m-complete at level $Sigma^0\_n$ 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^\{(omega)\}$.

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

cite book
author = Lerman, M.
year = 1983
title = Degrees of unsolvability: local and global theory
publisher = Berlin; New York: Springer-Verlag
isbn = 3-540-12155-2

cite book
author = Rogers Jr, H.
year = 1987
title = Theory of recursive functions and effective computability
publisher = MIT Press Cambridge, MA, USA
isbn = 0-07-053522-1

cite journal
author = Shore, R.A.
coauthors = Slaman, T.A.
year = 1999
title = Defining the Turing jump
journal = Math. Res. Lett.
volume = 6
issue = 5-6
pages = 711-722
url = http://www.mrlonline.org/mrl/1999-006-006/1999-006-006-010.pdf
accessdate = 2008-07-13

cite book
author = Soare, R.I.
year = 1987
title = Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets
publisher = Springer
isbn = 3-540-15299-7