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.

1 Definition
2 Examples
3 Properties
4 References

[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) \mathrm{is\;defined}\}.$

The nth Turing jump X⁽ⁿ⁾ 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 $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 $\emptyset'$ . Similarly, $0 (n)$ is the nth jump of the empty set.

[edit] Examples

$K_\varphi \equiv \varnothing'$ , the Turing jump 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 (ω)$ .

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

[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

Retrieved from "http://en.wikipedia.org../../../t/u/r/Turing_jump.html"

Category: Recursion theory

Turing jump

From Wikipedia, the free encyclopedia

Contents

[edit] Definition

[edit] Examples

[edit] Properties

[edit] References

Views

Navigation

Search

In other languages