Turing jump

From Wikipedia, the free encyclopedia

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.

Contents

[edit] 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'= \{x \mid \varphi_x^X(x) \ \mbox{is defined} \}.

The nth 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 \langle X^{(n)}\mid n \in \mathbb{N}\rangle:

X^{(\omega)} = \{p_i^k \mid k \in X^{(i)}\},\,

where pi denotes the ith prime.

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

\emptyset'.

Similarly, 0(n) is the nth jump of the empty set.

[edit] Examples

[edit] Properties

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

[edit] 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-7

Languages