Turing hopp

I beräkningsteorin är Turing -hopp- eller Turing-hoppoperatorn , $X uppkallad$ efter Alan Turing , en operation som tilldelar varje beslutsproblem $X$ ett successivt svårare beslutsproblem "med egenskapen att $X "$ inte kan avgöras av en orakelmaskin med ett orakel för $X.$ _

Operatören kallas en hoppoperator eftersom den ökar Turinggraden för problemet $X$ . Det vill säga, problemet $X'$ är inte Turing-reducerbart till $X$ . Posts teorem etablerar ett samband mellan Turing-hoppoperatorn och den aritmetiska hierarkin av uppsättningar av naturliga tal. Informellt, givet ett problem, returnerar Turing-hoppet uppsättningen Turing-maskiner som stannar när de ges tillgång till ett orakel som löser det problemet.

Definition

Turinghoppet av X kan ses som ett orakel till stoppproblemet för orakelmaskiner med ett orakel för X .

Formellt, givet en mängd $X$ och en Gödel-numrering $φ i X$ av de $X$ -beräknarbara funktionerna, definieras Turinghoppet $X'$ av $X som$

X'=\{x\mid \varphi _{x}^{X}(x)\ {\mbox{är definierad}}\}.

Det $n$ :te Turinghoppet $X (n)$ definieras induktivt av

X^{(0)}=X,

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

$ω$ -hoppet X $(ω)$ av $X$ är den effektiva sammanfogningen av sekvensen av mängder $X (n)$ för $n \in N$ :

X^{(\omega )}=\{p_{i}^{k}\mid i\in \ mathbb {N} {\text{ och }}k\in X^{(i)}\},

där $p i$ anger det i: $te$ primtal.

Notationen $0'$ eller $\emptyset'$ används ofta för Turing-hoppet i den tomma uppsättningen. Den läses nollhopp eller ibland nollprimtal .

På liknande sätt är $0 (n) det$ $n$ :te hoppet i den tomma uppsättningen. För finita $n$ är dessa mängder nära besläktade med den aritmetiska hierarkin , och är särskilt kopplade till Posts sats .

Hoppet kan itereras till transfinita ordinaler : det finns hoppoperatorer $j^{\delta }$ för uppsättningar av naturliga tal när $\delta$ är en ordinal som har en kod i Kleenes ${\ displaystyle {\mathcal {O}}}$ (oavsett kod är de resulterande hoppen desamma med ett teorem av Spector), i synnerhet mängderna $0 (α)$ för $α < ω 1 CK$ , där $ω 1 CK$ är Church–Kleene ordinal , är nära besläktade med den hyperaritmetiska hierarkin . Bortom $ω 1 CK$ , kan processen fortsättas genom de räknebara ordinalerna i det konstruerbara universum , med hjälp av Jensens arbete med finstrukturteori av Godels L . Konceptet har också generaliserats för att sträcka sig till oräkneliga vanliga kardinaler .

Exempel

Turinghoppet $0'$ i den tomma uppsättningen motsvarar Turing- problemet .
För varje $n$ är mängden $0 (n)$ m-komplett på nivå $\Sigma _{n}^{0}$ i den aritmetiska hierarkin (enligt Posts sats ).
Peano-arithmetikens språk med ett predikat för $X$ kan beräknas från $X (ω)$ .

Egenskaper

$X'$ är $X$ - beräknarbart uppräknat men inte $X$ - beräknarbart .
Om $A$ är Turing-ekvivalent med $B$ , så är $A'$ Turing-ekvivalent med $B'$ . Motsatsen till denna implikation är inte sann.
( Shore och Slaman , 1999) Funktionsavbildningen $X$ till $X'$ är definierbar i partiell ordning av Turinggraderna.

Många egenskaper hos Turing-hoppoperatören diskuteras i artikeln om Turing-grader .

Ambos-Spies, K. och Fejer, P. Grader av olöslighet. Opublicerad. http://www.cs.umb.edu/~fejer/articles/History_of_Degrees.pdf
Lerman, M. (1983). Grader av olöslighet: lokal och global teori . Berlin; New York: Springer-Verlag . ISBN 3-540-12155-2 .
Lubarsky, Robert S. (dec 1987). "Oräkneliga masterkoder och hopphierarkin". Journal of Symbolic Logic . Vol. 52, nr. 4. s. 952–958. JSTOR 2273829 .
Rogers Jr, H. (1987). Teori om rekursiva funktioner och effektiv beräkningsbarhet . MIT Press , Cambridge, MA, USA. ISBN 0-07-053522-1 .
Shore, RA; Slaman, TA (1999). "Definiera Turing-hoppet" (PDF) . Matematiska forskningsbrev . 6 (5–6): 711–722. doi : 10.4310/mrl.1999.v6.n6.a10 . Hämtad 2008-07-13 .
Soare, RI (1987). Rekursivt uppräknade uppsättningar och grader: En studie av beräkningsbara funktioner och beräkningsbart genererade uppsättningar . Springer. ISBN 3-540-15299-7 .