Turingův skok - Turing jump

v teorie vypočítatelnosti, Turingův skok nebo Turingův operátor skoku, pojmenovaný pro Alan Turing, je operace, která je každému přiřazena rozhodovací problém $X$ postupně těžší rozhodovací problém $X'$ s majetkem, který $X'$ není rozhodnutelný pomocí věštecký stroj s věštec pro $X$ .

Operátor se nazývá a operátor skoku protože zvyšuje Turingův stupeň problému $X$ . To je ten problém $X'$ není Turingově redukovatelný na $X$ . Postova věta navazuje vztah mezi operátorem Turingova skoku a aritmetická hierarchie množin přirozených čísel.^[1] Neformálně, vzhledem k problému, Turingův skok vrací sadu Turingových strojů, které se zastaví, když jim bude poskytnut přístup k věštci, který tento problém vyřeší.

Definice

Turingův skok X lze považovat za věštce pro zastavení problému pro věštecké stroje s věštcem na X.^[1]

Formálně, vzhledem k sadě $X$ a a Gödelovo číslování $φ i X$ z $X$ -vypočitatelný funkce, Turingův skok $X'$ z $X$ je definován jako

{ displaystyle X '= {x mid varphi _ {x} ^ {X} (x) { mbox {je definováno}} }.}

The $n$ th Turingův skok $X (n)$ je definována indukčně

{ displaystyle X ^ {(0)} = X,}

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

The $ω$ skok $X (ω)$ z $X$ je efektivní spojení sekvence sad $X (n)$ pro $n \in N$ :

{ displaystyle X ^ {( omega)} = {p_ {i} ^ {k} mid i in mathbb {N} { text {a}} k v X ^ {(i)} },}

kde $p i$ označuje $i$ th prime.

Zápis $0'$ nebo $\emptyset'$ se často používá pro Turingův skok prázdné sady. Je to přečteno nulový skok nebo někdy nultý prime.

Podobně, $0 (n)$ je $n$ th skok prázdné sady. Pro konečné $n$ , tyto sady úzce souvisí s aritmetická hierarchie.

Skok lze iterovat do transfinitních ordinálů: množin $0 (α)$ pro $α <ω 1 CK$ , kde $ω 1 CK$ je Církev – Kleene ordinální, úzce souvisí s hyperaritmetická hierarchie.^[1] Mimo $ω 1 CK$ , proces může pokračovat přes spočítatelné řadové řádky konstruovatelný vesmír, s využitím množinově-teoretických metod (Hodes 1980). Koncept byl také zobecněn, aby se rozšířil na nespočet řádní kardinálové (Lubarsky 1987).^[2]

Příklady

Turingův skok $0'$ prázdné sady je Turing ekvivalentní s zastavení problému.^[3]
Pro každého $n$ , sada $0 (n)$ je m-kompletní na úrovni ${ displaystyle Sigma _ {n} ^ {0}}$ v aritmetická hierarchie (podle Postova věta ).
Sada Gödelových čísel skutečných vzorců v jazyce Peano aritmetika s predikátem pro $X$ je vypočítatelný z $X (ω)$ .^[4]

Vlastnosti

$X'$ je $X$ -vypočítatelně vyčíslitelné ale ne $X$ -vypočitatelný.
Li $A$ je Turingův ekvivalent na $B$ , pak $A'$ je Turingův ekvivalent $B'$ . Opak této implikace není pravdivý.
(Pobřeží a Slaman, 1999) Mapování funkcí $X$ na $X'$ je definovatelný v částečném pořadí Turingových stupňů.^[3]

Mnoho vlastností operátoru Turingova skoku je popsáno v článku o Turingovy stupně.

Reference

^ ^A ^b ^C Ambos-Spies, Klaus; Fejer, Peter A. (2014), „Stupně neřešitelnosti“, Příručka dějin logiky, Elsevier, 9, str. 443–494, doi:10.1016 / b978-0-444-51624-4.50010-1, ISBN 9780444516244.
^ Lubarsky, Robert S. (prosinec 1987). Msgstr "Nespočetné hlavní kódy a hierarchie skoků". The Journal of Symbolic Logic. 52 (4): 952–958. doi:10.2307/2273829. ISSN 0022-4812. JSTOR 2273829.
^ ^A ^b Shore, Richard A .; Slaman, Theodore A. (1999). „Definování Turingova skoku“. Dopisy o matematickém výzkumu. 6 (6): 711–722. doi:10.4310 / MRL.1999.v6.n6.a10.
^ Hodes, Harold T. (červen 1980). "Skok přes transfinit: hierarchie hlavního kódu Turingových stupňů". The Journal of Symbolic Logic. 45 (2): 204–220. doi:10.2307/2273183. ISSN 0022-4812. JSTOR 2273183.

Ambos-Spies, K. a Fejer, P. Stupně neřešitelnosti. Nepublikovaný. http://www.cs.umb.edu/~fejer/articles/History_of_Degrees.pdf
Hodes, Harold T. (červen 1980). „Jumping Through the Transfinite: The Master Code Hierarchy of Turing Degrees“. Journal of Symbolic Logic. Sdružení pro symbolickou logiku. 45 (2): 204–220. doi:10.2307/2273183. JSTOR 2273183.
Lerman, M. (1983). Stupně neřešitelnosti: lokální a globální teorie. Berlín; New York: Springer-Verlag. ISBN 3-540-12155-2.
Lubarsky, Robert S. (prosinec 1987). "Nespočetné hlavní kódy a hierarchie skoků". Journal of Symbolic Logic. 52 (4). 952–958. JSTOR 2273829.
Rogers Jr, H. (1987). Teorie rekurzivních funkcí a efektivní vypočítatelnost. MIT Stiskněte, Cambridge, MA, USA. ISBN 0-07-053522-1.
Shore, R.A .; Slaman, T.A. (1999). „Definování Turingova skoku“ (PDF). Dopisy o matematickém výzkumu. 6 (5–6): 711–722. doi:10.4310 / mrl.1999.v6.n6.a10. Citováno 2008-07-13.
Soare, RI (1987). Rekurzivně vyčíslitelné množiny a stupně: Studie vypočítatelných funkcí a vypočítatelně generovaných množin. Springer. ISBN 3-540-15299-7.

[:0-1] A ^b ^C Ambos-Spies, Klaus; Fejer, Peter A. (2014), „Stupně neřešitelnosti“, Příručka dějin logiky, Elsevier, 9, str. 443–494, doi:10.1016 / b978-0-444-51624-4.50010-1, ISBN 9780444516244.

[2] Lubarsky, Robert S. (prosinec 1987). Msgstr "Nespočetné hlavní kódy a hierarchie skoků". The Journal of Symbolic Logic. 52 (4): 952–958. doi:10.2307/2273829. ISSN 0022-4812. JSTOR 2273829.

[:1-3] A ^b Shore, Richard A .; Slaman, Theodore A. (1999). „Definování Turingova skoku“. Dopisy o matematickém výzkumu. 6 (6): 711–722. doi:10.4310 / MRL.1999.v6.n6.a10.

[4] Hodes, Harold T. (červen 1980). "Skok přes transfinit: hierarchie hlavního kódu Turingových stupňů". The Journal of Symbolic Logic. 45 (2): 204–220. doi:10.2307/2273183. ISSN 0022-4812. JSTOR 2273183.

[1]

[2]

[3]

[4]