Turing jump

The Turing jump of {{mvar|X}} can be thought of as an oracle to the halting problem for oracle machines with an oracle for {{mvar|X}}.

Formally, given a set {{mvar|X}} and a Gödel numbering {{math|φ_i^X}} of the relative computability functions, the Turing jump {{math|X′}} of {{mvar|X}} is defined as

$$X\text{'}=\; \backslash \{x\; \backslash mid\; \backslash varphi\_x^X(x)\; \backslash \; \backslash mbox\{is\; defined\}\; \backslash \}.$$

The {{mvar|n}}th Turing jump {{math|X⁽ⁿ⁾}} is defined inductively by

$$\backslash begin\{align\}$$

X^{(0)} &= X,\\

X^{(n+1)} &= X^{(n)}{'}.

\end{align}

The {{math|ω}} jump {{math|X^(ω)}} of {{math|X}} is the effective join of the sequence of sets {{math|X⁽ⁿ⁾}} for {{math|n ∈ Natural numbers}}:

$$X^\{(\backslash omega)\}\; =\; \backslash \{p\_i^k\; \backslash mid\; i\; \backslash in\; \backslash mathbb\{N\}\; \backslash text\{\; and\; \}\; k\; \backslash in\; X^\{(i)\}\backslash \},$$

where {{math|p_i}} denotes the {{mvar|i}}th prime.

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

Similarly, {{math|0⁽ⁿ⁾}} is the {{mvar|n}}th jump of the empty set. For finite {{mvar|n}}, these sets are closely related to the arithmetic hierarchy,S. G. Simpson, [http://personal.psu.edu/t20/papers/jump-hierarchy-1980.pdf "The Hierarchy Based on the Jump Operator"], p.269. The Kleene Symposium (North-Holland, 1980) and is in particular connected to Post's theorem.

The jump can be iterated into transfinite ordinals: there are jump operators $j^\backslash delta$ for sets of natural numbers when $\backslash delta$ is an ordinal that has a code in Kleene's $\backslash mathcal\; O$ (regardless of code, the resulting jumps are the same by a theorem of Spector), in particular the sets {{math|0^(α)}} for {{math|α < ω₁^CK}}, where {{math|ω₁^CK}} is the Church–Kleene ordinal, are closely related to the hyperarithmetic hierarchy. Beyond {{math|ω₁^CK}}, 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.{{cite journal | title=Jumping Through the Transfinite: The Master Code Hierarchy of Turing Degrees | last=Hodes | first=Harold T. | journal=Journal of Symbolic Logic | volume=45 |date=June 1980 | pages=204–220 | publisher=Association for Symbolic Logic | jstor=2273183 | issue=2 | doi=10.2307/2273183

| s2cid=41245500 | url=https://philarchive.org/rec/HODJTT }} The concept has also been generalized to extend to uncountable regular cardinals.{{Cite journal |last=Lubarsky |first=Robert S. |date=December 1987 |title=Uncountable master codes and the jump hierarchy |journal=The Journal of Symbolic Logic |volume=52 |issue=4 |pages=952–958 |doi=10.2307/2273829 |issn=0022-4812 |jstor=2273829|s2cid=46113113 }}

• The Turing jump {{math|0′}} of the empty set is Turing equivalent to the halting problem.{{Cite journal|last1=Shore|first1=Richard A.|last2=Slaman|first2=Theodore A.|date=1999|title=Defining the Turing Jump|journal=Mathematical Research Letters|volume=6|issue=6|pages=711–722|doi=10.4310/MRL.1999.v6.n6.a10|doi-access=free}}
• For each {{math|n}}, the set {{math|0⁽ⁿ⁾}} is m-complete at level $\backslash Sigma^0\_n$ in the arithmetical hierarchy (by Post's theorem).
• The set of Gödel numbers of true formulas in the language of Peano arithmetic with a predicate for {{math|X}} is computable from {{math|X^(ω)}}.{{Cite journal|last=Hodes|first=Harold T.|date=June 1980|title=Jumping through the transfinite: the master code hierarchy of Turing degrees|journal=The Journal of Symbolic Logic|volume=45|issue=2|pages=204–220|doi=10.2307/2273183|issn=0022-4812|jstor=2273183|s2cid=41245500 |url=https://philarchive.org/rec/HODJTT }}

• {{math|X′}} is {{math|X}}-computably enumerable but not {{math|X}}-computable.
• If {{math|A}} is Turing-equivalent to {{math|B}}, then {{math|A′}} is Turing-equivalent to {{math|B′}}. The converse of this implication is not true.
• (Shore and Slaman, 1999) The function mapping {{math|X}} to {{math|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 degrees.

{{Reflist}}

• 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-2

}}

• {{cite news

| author = Lubarsky, Robert S.

| title = Uncountable Master Codes and the Jump Hierarchy

| journal = Journal of Symbolic Logic

| volume = 52

| issue = 4

|date=Dec 1987

| pages = 952–958

| jstor = 2273829

}}

• {{cite 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-1

}}

• {{cite journal

| author = Shore, R.A.

|author2=Slaman, T.A.

| year = 1999

| title = Defining the Turing jump

| journal = Mathematical Research Letters

| volume = 6

| issue = 5–6

| pages = 711–722

| url = http://math.berkeley.edu/~slaman/papers/jump.pdf

| accessdate = 2008-07-13

| doi=10.4310/mrl.1999.v6.n6.a10

| doi-access = free

}}

• {{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

}}

Category:Year of introduction missing

Category:Computability theory

Category:Alan Turing