- Turing jump
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 machinewith an oracle for "X".
The operator is called a "jump operator" because it increases the
Turing degreeof the problem "X". That is, the problem "X"′ is not Turing reducibleto "X". Post's theoremestablishes a relationship between the Turing jump operator and the arithmetical hierarchyof sets of natural numbers.
Given a set "X" and a
Gödel numberingof the "X"-computable functions, the Turing jump "X"′ of "X" is defined as
The "n"th Turing jump "X"("n") is defined inductively by::
The ω jump "X"(ω) of "X" is the
effective joinof the sequence of sets :
where 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
Similarly, is the "n"th jump of the empty set.
* The Turing jump of the empty set is Turing equivalent to the
* For each "n", the set is
m-completeat level in the arithmetical hierarchy.
* The set of Gödel numbers of true formulas in the language of
Peano arithmeticwith a predicate for "X" is computable from .
* "X"′ is "X"-
computably enumerablebut 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
Ambos-Spies, K. and Fejer, P. Degrees of Unsolvability. Unpublished. http://www.cs.umb.edu/~fejer/articles/History_of_Degrees.pdf
author = Lerman, M.
year = 1983
title = Degrees of unsolvability: local and global theory
publisher = Berlin; New York: Springer-Verlag
isbn = 3-540-12155-2
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
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
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