computability theory Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since e ...

, the Turing jump or Turing jump operator, named for

Alan Turing Alan Mathison Turing (; 23 June 1912 – 7 June 1954) was an English mathematician, computer scientist, logician, cryptanalyst, philosopher, and theoretical biologist. Turing was highly influential in the development of theoretical com ...

, is an operation that assigns to each

decision problem In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm whethe ...

a successively harder decision problem with the property that is not decidable by an

oracle machine In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to solve certain problems in a s ...

with an

oracle An oracle is a person or agency considered to provide wise and insightful counsel or prophetic predictions, most notably including precognition of the future, inspired by deities. As such, it is a form of divination. Description The word '' ...

for . The operator is called a ''jump operator'' because it increases the

Turing degree In computer science and mathematical logic the Turing degree (named after Alan Turing) or degree of unsolvability of a set of natural numbers measures the level of algorithmic unsolvability of the set. Overview The concept of Turing degree is fund ...

of the problem . That is, the problem is not Turing-reducible to .

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 uses several concepts relating to definability and re ...

establishes a relationship between the Turing jump operator and the

arithmetical hierarchy In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene–Mostowski hierarchy (after mathematicians Stephen Cole Kleene and Andrzej Mostowski) classifies certain sets based on the complexity of formulas that define th ...

of sets of natural numbers.. Informally, given a problem, the Turing jump returns the set of Turing machines that halt when given access to an oracle that solves that problem.

Definition

The Turing jump of ''X'' can be thought of as an oracle to the

halting problem In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. Alan Turing proved in 1936 that a g ...

for

s with an oracle for ''X''. Formally, given a set and a

Gödel numbering In mathematical logic, a Gödel numbering is a function that assigns to each symbol and well-formed formula of some formal language a unique natural number, called its Gödel number. The concept was developed by Kurt Gödel for the proof of his ...

of the -computable functions, the Turing jump of is defined as :

X'= \.

The th Turing jump is defined inductively by :

X^ = X,

X^ = (X^)'.

The jump of is the effective join of the sequence of sets for : :

X^ = \,

where denotes the th prime. The notation or is often used for the Turing jump of the empty set. It is read ''zero-jump'' or sometimes ''zero-prime''. Similarly, is the th jump of the empty set. For finite , these sets are closely related to the

arithmetic hierarchy In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene–Mostowski hierarchy (after mathematicians Stephen Cole Kleene and Andrzej Mostowski) classifies certain sets based on the complexity of formulas that define t ...

. The jump can be iterated into transfinite ordinals: the sets for , where is the

Church–Kleene ordinal In mathematics, particularly set theory, non-recursive ordinals are large countable ordinals greater than all the recursive ordinals, and therefore can not be expressed using ordinal collapsing functions. The Church–Kleene ordinal and varian ...

, are closely related to the

hyperarithmetic hierarchy 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 importa ...

. Beyond , the process can be continued through the countable ordinals of the

constructible universe In mathematics, in set theory, the constructible universe (or Gödel's constructible universe), denoted by , is a particular class of sets that can be described entirely in terms of simpler sets. is the union of the constructible hierarchy . It w ...

, using set-theoretic methods (Hodes 1980). The concept has also been generalized to extend to uncountable

regular cardinal In set theory, a regular cardinal is a cardinal number that is equal to its own cofinality. More explicitly, this means that \kappa is a regular cardinal if and only if every unbounded subset C \subseteq \kappa has cardinality \kappa. Infinite ...

s (Lubarsky 1987).

Examples

* The Turing jump of the empty set is Turing equivalent to the

. * For each , the set is

m-complete In computability theory and computational complexity theory, a many-one reduction (also called mapping reduction) is a reduction which converts instances of one decision problem L_1 into instances of a second decision problem L_2 where the insta ...

at level

\Sigma^0_n

in the

(by

). * The set of Gödel numbers of true formulas in the language of

Peano arithmetic In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano. These axioms have been used nearly u ...

with a predicate for is computable from .

Properties

* is -

computably enumerable In computability theory, a set ''S'' of natural numbers is called computably enumerable (c.e.), recursively enumerable (r.e.), semidecidable, partially decidable, listable, provable or Turing-recognizable if: *There is an algorithm such that the ...

but not -

computable Computability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is close ...

. * If is Turing-equivalent to , then is Turing-equivalent to . The converse of this implication is not true. * (

Shore A shore or a shoreline is the fringe of land at the edge of a large body of water, such as an ocean, sea, or lake. In physical oceanography, a shore is the wider fringe that is geologically modified by the action of the body of water past a ...

and Slaman, 1999) The function mapping to is definable in the

partial order In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary ...

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

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 = 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 Year of introduction missing Computability theory Alan Turing