Turing jump

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

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

Properties

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

References

  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.

Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!