Turing-Grad

In der Informatik und der mathematischen Logik misst der Turing-Grad (benannt nach Alan Turing ) oder Grad der Unlösbarkeit einer Menge natürlicher Zahlen den Grad der algorithmischen Unlösbarkeit der Menge.

Der Turinggrad ist ein grundlegendes Konzept der Berechenbarkeitstheorie , in der Mengen natürlicher Zahlen häufig als Entscheidungsprobleme betrachtet werden . Der Turinggrad einer Menge ist ein Maß dafür, wie schwierig es ist, das mit der Menge verbundene Entscheidungsproblem zu lösen, also zu bestimmen, ob eine beliebige Zahl in der gegebenen Menge enthalten ist.

Zwei Mengen sind Turing-äquivalent , wenn sie denselben Grad an Unlösbarkeit aufweisen. Jeder Turing-Grad ist eine Menge von Turing-äquivalenten Mengen, sodass zwei Mengen genau dann unterschiedliche Turing-Grade haben, wenn sie nicht Turing-äquivalent sind. Darüber hinaus sind die Turing-Grade partiell geordnet . Ist der Turing-Grad einer Menge X kleiner als der Turing-Grad einer Menge Y , so lässt sich jedes (möglicherweise nicht berechenbare) Verfahren, das korrekt entscheidet, ob Zahlen in Y enthalten sind , effektiv in ein Verfahren umwandeln, das korrekt entscheidet, ob Zahlen in X enthalten sind . In diesem Sinne entspricht der Turing-Grad einer Menge ihrem Grad an algorithmischer Unlösbarkeit.

Die Turing-Grade wurden von Post (1944) eingeführt , und viele grundlegende Ergebnisse wurden von Kleene und Post (1954) erzielt . Seitdem sind die Turing-Grade Gegenstand intensiver Forschung. Viele Beweise in diesem Bereich verwenden eine Beweistechnik, die als Prioritätsmethode bekannt ist .

Im Folgenden bezeichnet der Begriff „Menge “ die Menge der natürlichen Zahlen. Eine Menge X heißt Turing-reduzierbar auf eine Menge Y , wenn es eine Orakel-Turingmaschine gibt, die anhand eines Orakels für die Zugehörigkeit zu Y die Zugehörigkeit zu X bestimmt . Die Notation X ≤ _T Y bedeutet, dass X Turing-reduzierbar auf Y ist .

Zwei Mengen X und Y heißen Turing-äquivalent , wenn X auf Y und Y auf X Turing-reduzierbar ist . Die Notation X ≡ _T Y bedeutet, dass X und Y Turing-äquivalent sind. Die Relation ≡ _T kann als Äquivalenzrelation verstanden werden , was bedeutet, dass für alle Mengen X , Y und Z gilt :

• X ≡ _T X
• X ≡ _T Y impliziert Y ≡ _T X
• Wenn X ≡ _T Y und Y ≡ _T Z , dann X ≡ _T Z.

Ein Turinggrad ist eine Äquivalenzklasse der Relation ≡ _T. Die Notation [ X ] bezeichnet die Äquivalenzklasse, die eine Menge X enthält . Die gesamte Menge der Turinggrade wird mit bezeichnet . ${\displaystyle {\mathcal {D}}}$

Die Turinggrade besitzen eine partielle Ordnung ≤, die so definiert ist, dass [ X ] ≤ [ Y ] genau dann gilt, wenn X ≤ _T Y. Es gibt einen eindeutigen Turinggrad, der alle berechenbaren Mengen enthält , und dieser Grad ist kleiner als jeder andere Grad. Er wird mit 0 (Null) bezeichnet, da er das kleinste Element der partiell geordneten Menge ist . (Üblicherweise werden Turinggrade fett gedruckt, um sie von Mengen zu unterscheiden. Wenn keine Verwechslungsgefahr besteht, wie beispielsweise bei [ X ], ist die Fettdruckung nicht notwendig.) ${\displaystyle {\mathcal {D}}}$

Für beliebige Mengen X und Y ist die Menge X ⊕ Y , geschrieben X ⊕ Y , definiert als die Vereinigung der Mengen {2 ⁿ  : n ∈ X } und {2 ^{m +1} : m ∈ Y }. Der Turinggrad von X ⊕ Y ist die kleinste obere Schranke der Grade von X und Y. Somit ist X ⊕ Y ein Vereinigungs-Halbverband . Die kleinste obere Schranke der Grade a und b wird mit a ∪ b bezeichnet . Es ist bekannt, dass X ⊕ Y kein Verband ist , da es Paare von Graden ohne größte untere Schranke gibt. ${\displaystyle {\mathcal {D}}}$${\displaystyle {\mathcal {D}}}$

Für jede Menge X bezeichnet die Notation X ′ die Menge der Indizes von Orakelmaschinen, die (bei Eingabe ihres Index) halten, wenn X als Orakel verwendet wird. Die Menge X ′ wird Turing-Sprung von X genannt . Der Turing-Sprung eines Grades [ X ] ist definiert als der Grad [ X ′]; dies ist eine gültige Definition, da X ′ ≡ _TY ′ gilt , wann immer X ≡ _TY . Ein wichtiges Beispiel ist 0 ′, der Grad des Halteproblems .

• Jeder Turinggrad ist abzählbar unendlich , das heißt, er enthält genau Mengen.${\displaystyle \aleph _{0}}$
• Es gibt verschiedene Turing-Grade.${\displaystyle 2^{\aleph _{0}}}$
• Für jeden Grad a gilt die strikte Ungleichung a < a ′.
• Für jeden Grad a ist die Menge der Grade unterhalb von a abzählbar . Die Menge der Grade oberhalb von a hat die Größe n .${\displaystyle 2^{\aleph _{0}}}$

Es wurden umfangreiche Forschungen zur Struktur der Turing-Grade durchgeführt. Die folgende Übersicht listet nur einige der vielen bekannten Ergebnisse auf. Eine allgemeine Schlussfolgerung, die sich aus der Forschung ziehen lässt, ist, dass die Struktur der Turing-Grade äußerst komplex ist.

• Es gibt minimale Grade . Ein Grad a ist minimal , wenn a ungleich null ist und es keinen Grad zwischen 0 und a gibt . Daher ist die Ordnungsrelation der Grade keine dichte Ordnung .
• Die Turinggrade sind nicht linear durch ≤ _T geordnet . ^{[ 1 ]}
• Tatsächlich gibt es zu jedem von Null verschiedenen Grad a einen Grad b , der mit a unvergleichbar ist .
• Es gibt eine Menge paarweise unvergleichbarer Turing-Grade.${\displaystyle 2^{\aleph _{0}}}$
• Es gibt Paare von Graden ohne größte untere Schranke. Daher ist es kein Verband .${\displaystyle {\mathcal {D}}}$
• Jede abzählbare, partiell geordnete Menge kann in die Turing-Grade eingebettet werden.
• Eine unendliche, streng monoton steigende Folge a ₁ , a ₂ , ... von Turinggraden kann keine kleinste obere Schranke haben, aber sie hat immer ein exaktes Paar c , d, so dass ∀ e ( e < c ∧ e < d ⇔ ∃ i e ≤ a _i ) (und somit hat sie obere Schranken).
• Unter der Annahme des Konstruierbarkeitsaxioms lässt sich zeigen, dass es eine maximale Kette von Graden vom Ordnungstyp gibt . ^{[ 2 ]}${\displaystyle \omega _{1}}$

• Zu jedem Grad a gibt es einen Grad, der strikt zwischen a und a ′ liegt. Tatsächlich gibt es eine abzählbar unendliche Familie paarweise unvergleichbarer Grade zwischen a und a ′.
• Sprunginversion: Ein Grad a ist genau dann von der Form b ′, wenn 0 ′ ≤ a .
• Zu jedem Grad a gibt es einen Grad b , so dass a < b und b ′ = a ′; ein solcher Grad b wird als niedrig relativ zu a bezeichnet .
• Es gibt eine unendliche Folge a _i von Graden, sodass a ′ _{i +1} ≤ a _i für jedes i gilt .
• Der Satz von Post stellt eine enge Korrespondenz zwischen der arithmetischen Hierarchie und endlich iterierten Turing-Sprüngen der leeren Menge her .

• Simpson (1977b) zeigte, dass die Prädikatenlogik erster Stufe in der Sprache ⟨ ≤, = ⟩ oder ⟨ ≤, ′, = ⟩ äquivalent zur Theorie der echten Arithmetik zweiter Stufe ist . Dies deutet darauf hin, dass die Struktur von äußerst komplex ist.${\displaystyle {\mathcal {D}}}$${\displaystyle {\mathcal {D}}}$
• Shore & Slaman (1999) zeigten, dass der Sprungoperator in der Struktur erster Stufe mit der Sprache ⟨ ≤, = ⟩ definierbar ist .${\displaystyle {\mathcal {D}}}$

Ein Grad heißt rekursiv aufzählbar (re) oder berechenbar aufzählbar (ce), wenn er eine rekursiv aufzählbare Menge enthält . Jeder re-Grad ist kleiner als 0 ′, aber nicht jeder Grad kleiner als 0 ′ ist re. Eine Menge ist jedoch genau dann n:1-reduzierbar auf 0 ′, wenn sie re ist. ^{[ 3 ]}${\displaystyle A}$${\displaystyle A}$

• Sacks (1964) : Die Re-Grade sind dicht beieinander; zwischen je zwei Re-Graden gibt es einen dritten Re-Grad.
• Lachlan (1966a) und Yates (1966) : Es gibt zwei Re-Grade ohne größte untere Schranke in den Re-Graden.
• Lachlan (1966a) und Yates (1966) : Es gibt ein Paar von re-Graden ungleich Null, deren größte untere Schranke 0 ist .
• Lachlan (1966b) : Es gibt kein Paar von re-Graden, deren größte untere Schranke 0 und deren kleinste obere Schranke 0 ′ ist. Dieses Ergebnis wird informell als Nicht-Diamant-Theorem bezeichnet .
• Thomason (1971) : Jeder endliche distributive Verband lässt sich in die Re-Grade einbetten. Tatsächlich kann die abzählbare atomlose Boolesche Algebra so eingebettet werden, dass Suprema und Infima erhalten bleiben .
• Lachlan & Soare (1980) : Nicht alle endlichen Verbände lassen sich in die Re-Grade einbetten (mittels einer Einbettung, die Suprema und Infima erhält). Ein konkretes Beispiel ist rechts dargestellt.
• LA Harrington und TA Slaman (siehe Nies, Shore & Slaman (1998) ): Die Theorie der re-Grade in der Sprache ⟨ 0 , ≤, = ⟩ ist n-1-äquivalent zur Theorie der wahren Arithmetik erster Stufe .

Darüber hinaus gibt es das Grenzwertlemma von Shoenfield: Eine Menge A erfüllt genau dann die Bedingung, wenn es eine „rekursive Approximation“ ihrer charakteristischen Funktion gibt: eine Funktion g, sodass für hinreichend große s gilt : . ^{[ 4 ]}${\displaystyle [A]\leq _{T}\emptyset '}$${\displaystyle g(s)=\chi _{A}(s)}$

Eine Menge A heißt n -r e, wenn es eine Familie von Funktionen gibt, sodass: ^{[ 4 ]}${\displaystyle (A_{s})_{s\in \mathbb {N} }}$

• As ist eine rekursive Approximation von A : Für ein t gilt für alle s ≥ t: _As ( x ) = A ( x ), wobei A insbesondere mit seiner charakteristischen Funktion gleichgesetzt wird. (Löscht man diese Bedingung auf _, erhält man die Definition, dass A „schwach n -re“ ist .)
• A _s ist ein " n -Versuchsprädikat": für alle x , A ₀ ( x )=0 und die Kardinalität von ist ≤ n .${\displaystyle \{s\mid A_{s}(x)\neq A_{s+1}(x)\}}$

Eigenschaften von n -re-Graden: ^{[ 4 ]}

• Die Klasse der Mengen vom n -re Grad ist eine strikte Unterklasse der Klasse der Mengen vom ( n +1)-re Grad.
• Für alle n > 1 gibt es zwei ( n + 1)-re Grade a , b mit , so dass das Segment keine n -re Grade enthält .${\displaystyle \mathbf {a} \leq _{T}\mathbf {b} }$${\displaystyle \{\mathbf {c} \mid \mathbf {a} \leq _{T}\mathbf {c} \leq _{T}\mathbf {b} \}}$
• ${\displaystyle A}$und sind ( n +1)-re genau dann, wenn beide Mengen schwach - n -re sind.${\displaystyle {\overline {A}}}$

Emil Post untersuchte die re-Turinggrade und fragte, ob es einen re-Grad gibt, der strikt zwischen 0 und 0 ′ liegt. Das Problem, einen solchen Grad zu konstruieren (oder zu zeigen, dass es keinen gibt), wurde als Postsches Problem bekannt . Dieses Problem wurde in den 1950er Jahren unabhängig voneinander von Friedberg und Muchnik gelöst , die die Existenz dieser intermediären re-Grade bewiesen ( Satz von Friedberg-Muchnik ). Ihre Beweise entwickelten jeweils dieselbe neue Methode zur Konstruktion von re-Graden, die als Prioritätsmethode bekannt wurde . Die Prioritätsmethode ist heute die wichtigste Technik, um Ergebnisse über re-Mengen zu beweisen.

Die Idee des Prioritätsverfahrens zur Konstruktion einer Menge X besteht darin, eine abzählbare Folge von Anforderungen an X zu erstellen . Um beispielsweise eine Menge X zwischen 0 und 0 ′ zu konstruieren, genügt es, für jede natürliche Zahl e die Anforderungen A _{_e} und B _{_e} zu erfüllen . Dabei fordert A _{_e}, dass die Orakelmaschine mit Index e 0′ nicht aus X berechnet, und B _{_e}, dass die Turingmaschine mit Index e (ohne Orakel) X nicht berechnet . Diese Anforderungen werden in einer Prioritätsordnung dargestellt , die eine explizite Bijektion der Anforderungen und der natürlichen Zahlen ist. Der Beweis verläuft induktiv mit einem Schritt für jede natürliche Zahl; diese Schritte können als Zeitabschnitte betrachtet werden, in denen die Menge X durchlaufen wird. In jedem Schritt können Zahlen in X aufgenommen oder dauerhaft (sofern sie nicht beschädigt werden) daran gehindert werden, in X aufgenommen zu werden , um die Anforderungen zu erfüllen (d. h., sie zu erzwingen, sobald X vollständig durchlaufen wurde). Manchmal kann eine Zahl in X aufgenommen werden , um eine Anforderung zu erfüllen. Dies führt jedoch dazu, dass eine zuvor erfüllte Anforderung nicht mehr erfüllt wird (d. h. verletzt wird ). Die Prioritätsreihenfolge der Anforderungen bestimmt, welche Anforderung in diesem Fall erfüllt werden muss. Die informelle Vorstellung ist, dass eine verletzte Anforderung erst dann wieder erfüllt ist, wenn alle Anforderungen höherer Priorität nicht mehr verletzt sind. Allerdings trifft dies nicht auf jedes Prioritätsargument zu. Es muss argumentiert werden, dass die Gesamtmenge X re ist und alle Anforderungen erfüllt. Prioritätsargumente können verwendet werden, um viele Aussagen über re-Mengen zu beweisen; die verwendeten Anforderungen und die Art und Weise ihrer Erfüllung müssen sorgfältig gewählt werden, um das gewünschte Ergebnis zu erzielen.

Beispielsweise kann ein einfaches (und daher nicht berechenbares) niedriges X (niedrig bedeutet X ′ = 0′) in unendlich vielen Schritten wie folgt konstruiert werden. Zu Beginn von Schritt n sei T _{_n} das Ausgabeband (binär), identifiziert durch die Menge der Zellindizes, an denen bisher 1 platziert wurde (also X = ∪_{_n} T _{_n} ; T _₀ = ∅) ; und P _{_n} ( m ) sei die Priorität, an Position m keine 1 auszugeben ; P _₀ ( m ) = ∞ . In Schritt n wird, falls möglich (ansonsten wird nichts unternommen), das kleinste i < n gewählt, sodass ∀m P _{_n} ( m ) ≠ i und die Turingmaschine i bei einer Eingabe S ⊇ T _{_n} mit ∀m ∈ S \ T_n P _{_n} ( m ) ≥ i in < n Schritten anhält . Wähle eine beliebige (endliche) Menge S , setze T _{_{n +1}} = S und setze für jede von Maschine i besuchte Zelle m auf S P _{_{n +1}} ( m ) = min( i , P _{_n} ( m )). Setze alle Prioritäten > i auf ∞ und anschließend eine beliebige Zelle mit Priorität ∞, die nicht zu S gehört, auf Priorität i . Im Wesentlichen bringen wir Maschine i zum Anhalten, sofern dies möglich ist, ohne Prioritäten < i zu beeinträchtigen , und setzen dann Prioritäten so, dass Maschinen > i das Anhalten nicht stören können; alle Prioritäten bleiben schließlich konstant.

Um zu sehen, dass X niedrig ist, hält Maschine i genau dann auf X , wenn sie in weniger als n Schritten auf einem T _{_n} hält, sodass Maschinen < i , die auf X halten , dies in weniger als n − i Schritten tun (rekursiv lässt sich dies gleichmäßig aus 0′ berechnen). X ist nicht berechenbar, da andernfalls eine Turingmaschine genau dann auf Y halten könnte, wenn Y \ X nicht leer ist, was der Konstruktion widerspricht, da X für beliebig große i einige Zellen der Priorität i ausschließt ; und X ist einfach, da für jedes i die Anzahl der Zellen der Priorität i endlich ist.

• Martin-Maß

• Cooper, S. B. (2004). Computability theory . Boca Raton, FL: Chapman & Hall/CRC. S. 424. ISBN 1-58488-237-9Die
• Cutland, Nigel J. (1980). Berechenbarkeit: Eine Einführung in die Theorie rekursiver Funktionen . Cambridge-New York: Cambridge University Press. S. 251. ISBN 0-521-22384-9DieISBN​ 0-521-29465-7

• Ambos-Spies, Klaus; Fejer, Peter (20. März 2006). „Grade der Unlösbarkeit“ (PDF) . Abgerufen am 20. August 2023. Unveröffentlicht .
• Epstein, R. L.; Haas, R.; Kramer, L. R. (1981). Leman, M.; Schmerl, J.; Soare, R. (Hrsg.). Hierarchien von Mengen und Grade unter 0. Lecture Notes in Mathematics. Band 859. Springer-Verlag.
• Lerman, M. (1983). Grade der Unlösbarkeit. Perspektiven der mathematischen Logik . Berlin: Springer-Verlag. ISBN 3-540-12155-2Die
• Odifreddi, Piergiorgio (1989). Klassische Rekursionstheorie . Studien zur Logik und den Grundlagen der Mathematik. Band 125. Amsterdam: North-Holland. ISBN 978-0-444-87295-1MR  0982269 .​
• Odifreddi, Piergiorgio (1999). Klassische Rekursionstheorie. Band II . Studien zur Logik und den Grundlagen der Mathematik. Band 143. Amsterdam: North-Holland. ISBN 978-0-444-50205-6MR  1718169 .​
• Rogers, Hartley (1967). Theorie rekursiver Funktionen und effektiver Berechenbarkeit . Cambridge, Massachusetts : MIT Press . ISBN 9780262680523OCLC 933975989. Abgerufen am  6. Mai 2020 .
• Sacks, G. E. (1966). Grade der Unlösbarkeit . Annalen der Mathematikstudien. Princeton University Press. ISBN 978-0-6910-7941-7. JSTOR  j.ctt1b9x0r8 .
• Simpson, Steven G. ( 1977a). „Grade der Unlösbarkeit: Eine Übersicht der Ergebnisse“. Annals of Mathematics Studies . Studies in Logic and the Foundations of Mathematics. 90. Elsevier : 631–652 . doi : 10.1016/S0049-237X(08)71117-0 . ISBN 9780444863881Die
• Shoenfield, Joseph R. (1971). Grade der Unlösbarkeit . North-Holland/Elsevier. ISBN 978-0-7204-2061-6Die
• Shore, R. (1993). „Die Theorien der T-, tt- und wtt-Re-Grade: Unentscheidbarkeit und darüber hinaus“. In: Univ. Nac. del Sur, Bahía Blanca (Hrsg.). Proceedings of the IX Latin American Symposium on Mathematical Logic, Part 1 (Bahía Blanca, 1992) . Notas Lógica Mat. Bd. 38, S.  61–70 .
• Soare, Robert Irving (1987). Rekursiv aufzählbare Mengen und Grade: Eine Studie über berechenbare Funktionen und berechenbar erzeugte Mengen . Perspektiven der mathematischen Logik. Berlin: Springer-Verlag. ISBN 3-540-15299-7Die
• Soare, Robert Irving (1978). „Rekursiv aufzählbare Mengen und Grade“ . Bull . Amer. Math. Soc. 84 (6): 1149–1181 . doi : 10.1090/S0002-9904-1978-14552-2 . MR  0508451. S2CID 29549997  .

• Chong, CT; Yu, Liang (Dezember 2007). „Maximale Ketten in den Turinggraden“ . Journal of Symbolic Logic . 72 (4): 1219–1227 . doi : 10.2178 / jsl/1203350783 . JSTOR  27588601. S2CID  38576214 .
• DeAntonio, Jasper (24. September 2010). „Die Turing-Grade und ihre fehlende lineare Ordnung“ (PDF) . Abgerufen am 20. August 2023 .
• Kleene, Stephen Cole ; Post, Emil L. (1954), „Der obere Halbverband der Grade rekursiver Unlösbarkeit“, Annals of Mathematics , Zweite Serie, 59 (3): 379–407 , doi : 10.2307/1969708 , ISSN  0003-486X , JSTOR  1969708 , MR  0061078
• Lachlan, Alistair H. (1966a), "Lower Bounds for Pairs of Recursively Enumerable Degrees", Proceedings of the London Mathematical Society , 3 (1): 537– 569, CiteSeerX  10.1.1.106.7893 , doi : 10.1112/plms/s3-16.1.537 .
• Lachlan, Alistair H. (1966b), „Die Unmöglichkeit, relative Komplemente für rekursiv aufzählbare Grade zu finden“, J. Symb. Log. , 31 (3): 434– 454, doi : 10.2307/2270459 , JSTOR  2270459 , S2CID  30992462 .
• Lachlan, Alistair H.; Soare, Robert Irving (1980), „Nicht jeder endliche Verband ist in die rekursiv aufzählbaren Grade einbettbar“, Advances in Mathematics , 37 : 78–82 , doi : 10.1016/0001-8708(80)90027-4
• Nies, André; Shore, Richard A.; Slaman, Theodore A. (1998), „Interpretierbarkeit und Definierbarkeit in rekursiv aufzählbaren Graden“, Proceedings of the London Mathematical Society , 77 (2): 241–291 , CiteSeerX  10.1.1.29.9588 , doi : 10.1112/S002461159800046X , ISSN  0024-6115 , MR  1635141 , S2CID  16488410
• Post, Emil L. (1944), „Rekursiv aufzählbare Mengen positiver ganzer Zahlen und ihre Entscheidungsprobleme“, Bulletin of the American Mathematical Society , 50 (5): 284–316 , doi : 10.1090/S0002-9904-1944-08111-1 , ISSN  0002-9904 , MR  0010514
• Sacks, G. E. (1964), „Die rekursiv aufzählbaren Grade sind dicht“, Annals of Mathematics , Zweite Serie, 80 (2): 300–312 , doi : 10.2307/1970393 , JSTOR  1970393
• 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 , ISSN  1073-2780 , MR  1739227
• Simpson, Stephen G. (1977b). „Theorie erster Ordnung der Grade rekursiver Unlösbarkeit“. Annals of Mathematics . Zweite Serie. 105 (1): 121–139 . doi : 10.2307/1971028 . ISSN  0003-486X . JSTOR  1971028. MR  0432435 .
• Thomason, SK (1971), „Subblattices of the recursively enumerable degrees“, Z. Math. Logik Grundlag. Math. , 17 : 273– 280, doi : 10.1002/malq.19710170131
• Yates, CEM (1966), „Ein minimales Paar rekursiv aufzählbarer Grade“, Journal of Symbolic Logic , 31 (2): 159–168 , doi : 10.2307/2269807 , JSTOR  2269807 , S2CID  38778059