Turingův skok - Turing jump

V teorii vypočítatelnosti je Turingův skok nebo Turingův skokový operátor , pojmenovaný pro Alana Turinga , operace, která přiřadí každému rozhodovacímu problému X postupně těžší rozhodovací problém X ' s vlastností, že X ' není určitelný strojem Oracle s Oracle pro X .

Operátor se nazývá operátor skok , protože zvyšuje stupeň Turingova na problém X . To znamená, že problém X ' není Turing-redukovat na X . Postova věta vytváří vztah mezi Turingovým skokovým operátorem a aritmetickou hierarchií množin přirozených čísel. Vzhledem k problému neformálně Turingův skok vrátí sadu Turingových strojů, které se zastaví, když jim bude poskytnut přístup k věštci, který tento problém vyřeší.

Definice

Turingova skok X si lze představit jako věštec na váhavý problém pro věštce strojích s věštírna X .

Formálně, vzhledem k množině X a Gödelovu číslování φ _i ^X z X- výpočetních funkcí, je Turingův skok X ' z X definován jako

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

N th Turing skoku X ^{( n )} je definován induktivně pomocí

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

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

Ω skok X ^(ω) z X je efektivní spojit posloupnosti množin X ^{( n )} pro n ∈ N :

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

kde p _i označuje i- té prvočíslo.

Pro Turingův skok prázdné množiny se často používá zápis 0 ' nebo ∅ ′ . Je to čtení nulového skoku nebo někdy nulového prime .

Podobně 0 ^{( n )} je n- tý skok prázdné množiny. Pro konečné n jsou tyto množiny úzce spjaty s aritmetickou hierarchií .

Skok lze iterovat do transfinitních ordinálů : množiny 0 ^(α) pro α <ω ₁ ^CK , kde ω ₁ ^CK je církev – Kleene ordinál , úzce souvisí s hyperaritmetickou hierarchií . Za hranicí ω ₁ ^CK lze v procesu pokračovat spočítatelnými řadovými čísly konstruovatelného vesmíru pomocí množinově-teoretických metod (Hodes 1980). Koncept byl rovněž zobecněn tak, aby se rozšířil i na nespočetných pravidelných kardinálů (Lubarsky 1987).

Příklady

• Turingův skok 0 ' prázdné sady je Turingův ekvivalent problému zastavení .
• U každé n je množina 0 ^{( n )} je m-úplná úrovni v aritmetické hierarchii (od pošty teorému ). ${\ displaystyle \ Sigma _ {n} ^ {0}}$
• Sada Gödelových čísel skutečných vzorců v jazyce Peanoovy aritmetiky s predikátem pro X je vypočítatelná z X ^(ω) .

Vlastnosti

• X ′ je X - vypočítatelně vyčíslitelné, ale ne X - vypočítatelné .
• Pokud je Turing-ekvivalent k B , pak " je Turing-ekvivalentní B " . Opak této implikace není pravdivý.
• ( Shore a Slaman , 1999) Funkce mapující X na X ' je definovatelná v částečném pořadí Turingových stupňů.

Mnoho vlastností Turingova skokového operátoru je popsáno v článku o Turingových stupních .

Reference

• 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 Press , Cambridge, MA, USA. ISBN   0-07-053522-1 .
• Shore, RA; Slaman, TA (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 . CS1 maint: discouraged parameter ( link )
• 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 .