- Turing jump
In

computability theory , the**Turing jump**or**Turing jump operator**, named forAlan Turing , is intuitively described as an operation that assigns to eachdecision problem "X" a successively harder decision problem "X"′ with the property that "X"′ is not decidable by anoracle 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 notTuring reducible to "X".Post's theorem establishes a relationship between the Turing jump operator and thearithmetical 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\text{'}=\; \{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)\})\text{'}.\; ,$The

**ω jump**"X"^{(ω)}of "X" is theeffective 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\text{'}.$

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

**Examples*** The Turing jump $varnothing\text{'}$ of the empty set is Turing equivalent to the

halting problem .

* For each "n", the set $varnothing^\{(n)\}$ ism-complete at level $Sigma^0\_n$ in thearithmetical hierarchy .

* The set of Gödel numbers of true formulas in the language ofPeano 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 degree s.**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-2cite 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-1cite 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-13cite 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