Jump to content

Turing jump

From Wikipedia, the free encyclopedia

In computability theory, the Turing jump or Turing jump operator, named for Alan Turing, is 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] 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

[edit]

The Turing jump of X can be thought of as an oracle to the halting problem for oracle machines with an oracle for X.[1]

Formally, given a set X and a Gödel numbering φiX of the X-computable functions, the Turing jump X of X is defined as

The nth Turing jump X(n) is defined inductively by

The ω jump X(ω) of X is the effective join of the sequence of sets X(n) for nN:

where pi denotes the ith prime.

The notation 0′ or ∅′ is often used for the Turing jump of the empty set. It is read zero-jump or sometimes zero-prime.

Similarly, 0(n) is the nth jump of the empty set. For finite n, these sets are closely related to the arithmetic hierarchy,[2] and is in particular connected to Post's theorem.

The jump can be iterated into transfinite ordinals: there are jump operators for sets of natural numbers when is an ordinal that has a code in Kleene's (regardless of code, the resulting jumps are the same by a theorem of Spector),[2] in particular the sets 0(α) for α < ω1CK, where ω1CK is the Church–Kleene ordinal, are closely related to the hyperarithmetic hierarchy.[1] Beyond ω1CK, the process can be continued through the countable ordinals of the constructible universe, using Jensen's work on fine structure theory of Gödel's L.[3][2] The concept has also been generalized to extend to uncountable regular cardinals.[4]

Examples

[edit]

Properties

[edit]

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

References

[edit]
  1. ^ a b c Ambos-Spies, Klaus; Fejer, Peter A. (2014), "Degrees of Unsolvability", Handbook of the History of Logic, vol. 9, Elsevier, pp. 443–494, doi:10.1016/b978-0-444-51624-4.50010-1, ISBN 9780444516244.
  2. ^ a b c S. G. Simpson, The Hierarchy Based on the Jump Operator, p.269. The Kleene Symposium (North-Holland, 1980)
  3. ^ Hodes, Harold T. (June 1980). "Jumping Through the Transfinite: The Master Code Hierarchy of Turing Degrees". Journal of Symbolic Logic. 45 (2). Association for Symbolic Logic: 204–220. doi:10.2307/2273183. JSTOR 2273183. S2CID 41245500.
  4. ^ Lubarsky, Robert S. (December 1987). "Uncountable master codes and the jump hierarchy". The Journal of Symbolic Logic. 52 (4): 952–958. doi:10.2307/2273829. ISSN 0022-4812. JSTOR 2273829. S2CID 46113113.
  5. ^ a b Shore, Richard A.; Slaman, Theodore A. (1999). "Defining the Turing Jump". Mathematical Research Letters. 6 (6): 711–722. doi:10.4310/MRL.1999.v6.n6.a10.
  6. ^ Hodes, Harold T. (June 1980). "Jumping through the transfinite: the master code hierarchy of Turing degrees". The Journal of Symbolic Logic. 45 (2): 204–220. doi:10.2307/2273183. ISSN 0022-4812. JSTOR 2273183. S2CID 41245500.