Turing jump


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'= {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)})'. ,

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'.

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

Examples

* The Turing jump varnothing' 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


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Turing degree — Post s problem redirects here. For the other Post s problem , see Post s correspondence problem. In computer science and mathematical logic the Turing degree or degree of unsolvability of a set of natural numbers measures the level of algorithmic …   Wikipedia

  • Turing reduction — In computability theory, a Turing reduction from a problem A to a problem B, named after Alan Turing, is a reduction which solves A, assuming B is already known (Rogers 1967, Soare 1987). It can be understood as an algorithm that could be used to …   Wikipedia

  • Turing machine equivalents — Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine Read only right moving Turing Machines Probabilistic Turing machine Multi track Turing machine Turing machine… …   Wikipedia

  • Turing's proof — First published in January 1937 with the title On Computable Numbers, With an Application to the Entscheidungsproblem , Turing s proof was the second proof of the assertion (Alonzo Church proof was first) that some questions are undecidable :… …   Wikipedia

  • Turing machine — For the test of artificial intelligence, see Turing test. For the instrumental rock band, see Turing Machine (band). Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine… …   Wikipedia

  • Post–Turing machine — The article Turing machine gives a general introduction to Turing machines, while this article covers a specific class of Turing machines. A Post–Turing machine is a program formulation of an especially simple type of Turing machine, comprising a …   Wikipedia

  • Computability theory — For the concept of computability, see Computability. Computability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown …   Wikipedia

  • Recursion theory — Recursion theory, also called computability theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability… …   Wikipedia

  • Post's theorem — In computability theory Post s theorem, named after Emil Post, describes the connection between the arithmetical hierarchy and the Turing degrees. Background The statement of Post s theorem requires several concepts relating to definability and… …   Wikipedia

  • Hyperarithmetical theory — In recursion theory, hyperarithmetic theory is a generalization of Turing computability. It has close connections with definability in second order arithmetic and with weak systems of set theory such as Kripke–Platek set theory. It is an… …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.