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 Template:Math a successively harder decision problem Template:Math with the property that Template:Math is not decidable by an oracle machine with an oracle for Template:Math.

The operator is called a jump operator because it increases the Turing degree of the problem Template:Math. That is, the problem Template:Math is not Turing-reducible to Template:Math. 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 that halt when given access to an oracle that solves that problem.

Definition

The Turing jump of Template:Mvar can be thought of as an oracle to the halting problem for oracle machines with an oracle for Template:Mvar.

Formally, given a set Template:Mvar and a Gödel numbering Template:Math of the [[relative computability|Template:Mvar-computable]] functions, the Turing jump Template:Math of Template:Mvar is defined as

$$X^{\prime }=\{x\mid {\phi }_x^X(x)\text{is defined}\}.$$

The Template:Mvarth Turing jump Template:Math is defined inductively by

$$\begin{array}{cc}{X}^{(0)}& =X,\\ X^{(n+1)}& =X^{(n)}\text{'}.\end{array}$$

The Template:Math jump Template:Math of Template:Math is the effective join of the sequence of sets Template:Math for Template:Math:

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

where Template:Math denotes the Template:Mvarth prime.

The notation Template:Math or Template:Math is often used for the Turing jump of the empty set. It is read zero-jump or sometimes zero-prime.

Similarly, Template:Math is the Template:Mvarth jump of the empty set. For finite Template:Mvar, these sets are closely related to the arithmetic hierarchy, and is in particular connected to Post's theorem.

The jump can be iterated into transfinite ordinals: there are jump operators $j^{\delta }$ for sets of natural numbers when $\delta$ is an ordinal that has a code in Kleene's $𝒪$ (regardless of code, the resulting jumps are the same by a theorem of Spector), in particular the sets Template:Math for Template:Math, where Template:Math is the Church–Kleene ordinal, are closely related to the hyperarithmetic hierarchy. Beyond Template:Math, 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. The concept has also been generalized to extend to uncountable regular cardinals.

Examples

• The Turing jump Template:Math of the empty set is Turing equivalent to the halting problem.
• For each Template:Math, the set Template:Math is m-complete at level ${\mathrm{\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 Template:Math is computable from Template:Math.

Properties

• Template:Math is Template:Math-computably enumerable but not Template:Math-computable.
• If Template:Math is Turing-equivalent to Template:Math, then Template:Math is Turing-equivalent to Template:Math. The converse of this implication is not true.
• (Shore and Slaman, 1999) The function mapping Template:Math to Template:Math 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
• Template:Cite book
• Template:Cite news
• Template:Cite book
• Template:Cite journal
• Template:Cite book