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 Failed to parse (Missing texvc executable; please see math/README to configure.): \varphi_i^X

of the X-computable functions, the Turing jump X′ of X is defined as

Failed to parse (Missing texvc executable; please see math/README to configure.): X'= \{x \mid \varphi_x^X(x) \ \mbox{is defined} \}.

The nth Turing jump X⁽ⁿ⁾ is defined inductively by

Failed to parse (Missing texvc executable; please see math/README to configure.): X^{(0)} = X, \,

Failed to parse (Missing texvc executable; please see math/README to configure.): X^{(n+1)}=(X^{(n)})'. \,

The ω jump X^(ω) of X is the effective join of the sequence of sets Failed to parse (Missing texvc executable; please see math/README to configure.): \langle X^{(n)}\mid n \in \mathbb{N}\rangle

Failed to parse (Missing texvc executable; please see math/README to configure.): X^{(\omega)} = \{p_i^k \mid k \in X^{(i)}\},\,

where Failed to parse (Missing texvc executable; please see math/README to configure.): p_i

denotes the ith prime.

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

Failed to parse (Missing texvc executable; please see math/README to configure.): \emptyset'.

Similarly, Failed to parse (Missing texvc executable; please see math/README to configure.): 0^{(n)}

is the nth jump of the empty set.

Examples

• The Turing jump Failed to parse (Missing texvc executable; please see math/README to configure.): \varnothing'

of the empty set is Turing equivalent to the halting problem.

• For each n, the set Failed to parse (Missing texvc executable; please see math/README to configure.): \varnothing^{(n)}

is m-complete at level Failed to parse (Missing texvc executable; please see math/README to configure.): \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 Failed to parse (Missing texvc executable; please see math/README to configure.): 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.

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

Lerman, M. Degrees of unsolvability. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1983. ISBN 3-540-12155-2

Rogers, H. The Theory of Recursive Functions and Effective Computability, MIT Press. ISBN 0-262-68052-1; ISBN 0-07-053522-1

Soare, R. Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987. ISBN 3-540-15299-7eo:Vikipedio:Projekto matematiko/Salto de Turing