Turing-Grad - Turing degree

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

Überblick

Das Konzept des Turing-Grades ist grundlegend in der Berechenbarkeitstheorie , wo Mengen natürlicher Zahlen oft als Entscheidungsprobleme betrachtet werden . Der Turing-Grad einer Menge ist ein Maß dafür, wie schwierig es ist, das mit der Menge verbundene Entscheidungsproblem zu lösen, d. h. zu bestimmen, ob eine beliebige Zahl in der gegebenen Menge enthalten ist.

Zwei Mengen sind Turing-äquivalent, wenn sie den gleichen Grad an Unlösbarkeit aufweisen; Jeder Turing-Grad ist eine Sammlung von Turing-äquivalenten Mengen, so dass zwei Mengen genau dann in unterschiedlichen Turing-Graden sind, wenn sie nicht Turing-äquivalent sind. Darüber hinaus sind die Turing-Grade teilweise geordnet, sodass, wenn der Turing-Grad einer Menge X kleiner als der Turing-Grad einer Menge Y ist, jede (nicht berechenbare) Prozedur, die korrekt entscheidet, ob Zahlen in Y sind, effektiv in eine Prozedur umgewandelt werden kann, die entscheidet richtig, ob Zahlen in X sind . In diesem Sinne entspricht der Turing-Grad einer Menge ihrem Niveau der algorithmischen Unlösbarkeit.

Die Turing-Grade wurden von Emil Leon Post (1944) eingeführt, und viele grundlegende Ergebnisse wurden von Stephen Cole Kleene und Post (1954) aufgestellt. Die Turing-Abschlüsse sind seitdem ein Gebiet intensiver Forschung. Viele Proofs in diesem Bereich verwenden eine Proof-Technik, die als Prioritätsmethode bekannt ist .

Turing-Äquivalenz

Für den Rest dieses Artikels bezieht sich das Wort Menge auf eine Menge natürlicher Zahlen. Eine Menge X heißt Turing, die auf eine Menge Y reduzierbar ist , wenn es eine Orakel-Turing-Maschine gibt , die über die Mitgliedschaft in X entscheidet, wenn ein Orakel für die Mitgliedschaft in Y gegeben wird . Die Notation X ≤ _T Y zeigt an, dass X Turing-reduzierbar auf Y ist .

Zwei Mengen X und Y werden als Turing-äquivalent definiert, wenn X Turing-reduzierbar auf Y und Y Turing-reduzierbar auf X ist . Die Notation X ≡ _T Y zeigt an, dass X und Y Turing-Äquivalent sind. Die Relation ≡ _T kann als Äquivalenzrelation angesehen 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 Turing-Grad ist eine Äquivalenzklasse der Relation ≡ _T . Die Notation [ X ] bezeichnet die Äquivalenzklasse, die eine Menge X enthält . Die gesamte Sammlung von Turing-Graden ist mit bezeichnet . ${\displaystyle {\mathcal {D}}}$

Turing Grad haben eine partielle Ordnung ≤ definiert , so dass [ X ] ≤ [ Y ] , wenn und nur wenn X ≤ _T Y . Es gibt einen einzigartigen Turing-Grad, der alle berechenbaren Mengen enthält, und dieser Grad ist kleiner als jeder andere Grad. Es wird mit 0 (Null) bezeichnet, weil es das kleinste Element des Poset ist . (Es ist üblich, Turing-Grade fett zu schreiben, um sie von Mengen zu unterscheiden. Wenn keine Verwechslungen auftreten können, wie bei [ X ], ist die fette Schrift nicht erforderlich.) ${\displaystyle {\mathcal {D}}}$

Für alle Sätze X und Y , X kommen Y, geschrieben X ⊕ Y , ist definiert als die Vereinigung der Mengen sein {2 n  : n ∈ X } und {2 m +1: m ∈ Y }. Der Grad der Turing X ⊕ Y ist die kleinste obere gebundene der Grad von X und Y . Somit ist ein Join-Halbgitter . Die kleinste obere Grad gebunden ein und b bezeichnet ist ein ∪ b . Es ist bekannt, dass dies kein Gitter ist , da es Gradpaare 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 anhalten (wenn ihr Index als Eingabe gegeben wird), wenn X als Orakel verwendet wird. Die Menge X ′ heißt Turing-Sprung von X . Der Turing-Sprung eines Grades [ X ] ist definiert als der Grad [ X ′]; Dies ist eine gültige Definition , da X '≡ _T Y ' , wenn X ≡ _T Y . Ein wichtiges Beispiel ist 0 ′, der Grad des Halteproblems .

Grundlegende Eigenschaften der Turing-Grade

• Jeder Turinggrad ist abzählbar unendlich , d.h. er enthält exakt 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 ein , die Menge des Grades unter a ist zählbar . Der Satz von Graden größer als a hat die Größe .${\displaystyle 2^{\aleph _{0}}}$

Struktur der Turing-Grade

Über die Struktur der Turing-Grade wurde viel geforscht. Die folgende Umfrage listet nur einige der vielen bekannten Ergebnisse auf. Eine allgemeine Schlussfolgerung, die aus der Forschung gezogen werden kann, ist, dass die Struktur der Turing-Grade äußerst kompliziert ist.

Bestelleigenschaften

• Es gibt minimale Abschlüsse . Ein Grad a ist minimal, wenn a ungleich Null ist und kein Grad zwischen 0 und a liegt . Somit ist die Ordnungsbeziehung auf den Graden keine dichte Ordnung .
• Für jeden Grad a ungleich null gibt es einen Grad b, der mit a nicht vergleichbar ist .
• Es gibt eine Menge von paarweise nicht vergleichbaren Turinggraden.${\displaystyle 2^{\aleph _{0}}}$
• Es gibt Gradpaare ohne größte untere Schranke. Somit ist kein Gitter.${\displaystyle {\mathcal {D}}}$
• Jede abzählbare teilgeordnete Menge kann in die Turing-Grade eingebettet werden.
• Keine unendliche, streng ansteigende Gradfolge hat eine kleinste obere Schranke.

Eigenschaften mit dem Sprung

• Für jeden Grad a gibt es einen Grad streng zwischen a und a′ . Tatsächlich gibt es eine abzählbare Familie von paarweise nicht vergleichbaren Graden zwischen a und a′ .
• Sprungumkehr: a Grad a hat die Form b′ genau dann, wenn 0′ ≤ a .
• Für jeden Grad eines gibt es ein gewisses Maß b , so dass ein < b und b ' = a' ; ein solcher Grad b heißt relativ zu a niedrig .
• Es gibt eine unendliche Folge a _i von Graden, so dass a ′ _{i +1} ≤ a _i für jedes i .

Logische Eigenschaften

• Simpson (1977) zeigt , dass die erste Ordnung Theorie des in der Sprache ⟨≤ =⟩ oder ⟨≤ ', =⟩ ist viel ein Äquivalent der Theorie der wahren zweite Ordnung Arithmetik . Dies weist darauf hin, dass die Struktur von extrem kompliziert ist.${\displaystyle {\mathcal {D}}}$${\displaystyle {\mathcal {D}}}$
• Shore und Slaman (1999) zeigten, dass der Sprungoperator in der Struktur erster Ordnung von mit der Sprache ⟨ ≤, = ⟩ definierbar ist .${\displaystyle {\mathcal {D}}}$

Rekursiv aufzählbare Turing-Grade

Ein endliches Gitter, das nicht in die re Grade eingebettet werden kann.

Ein Grad heißt rekursiv aufzählbar (re), wenn er eine rekursiv aufzählbare Menge enthält . Jeder Grad re ist unter 0′ , aber nicht jeder Grad unter 0′ ist re.

• ( GE Sacks , 1964) Die Regrade sind dicht; Zwischen zwei beliebigen Re-Graden gibt es einen dritten Re-Grad.
• (AH Lachlan, 1966a und CEM Yates, 1966) Es gibt zwei Re-Grade ohne größte untere Grenze in den Re-Graden.
• (AH Lachlan, 1966a und CEM Yates, 1966) Es gibt ein Paar von Graden ungleich null, deren größte untere Grenze 0 ist .
• (AH Lachlan, 1966b) Es gibt kein Paar von re-Graden, dessen größte untere Schranke 0 und dessen kleinste obere Schranke 0′ ist . Dieses Ergebnis wird informell das Nichtdiamant-Theorem genannt .
• (SK Thomason, 1971) Jedes endliche Verteilungsgitter kann in die re Grade eingebettet werden. Tatsächlich kann die zählbare atomlose Boolesche Algebra so eingebettet werden, dass Suprema und Infima erhalten bleiben .
• (AH Lachlan und RI Soare , 1980) Nicht alle endlichen Gitter können in die re Grade eingebettet werden (über eine Einbettung, die Suprema und Infima bewahrt). Ein besonderes Beispiel ist rechts dargestellt.
• ( LA Harrington und TA Slaman siehe Nies, Shore und Slaman (1998)) erster Ordnung Theorie der re Grad in der Sprache ⟨ 0 , ≤ =⟩ ist viel ein Äquivalent der Theorie der wahren erster Ordnung Arithmetik .

Das Problem der Post und die Prioritätsmethode

Emil Post untersuchte die re Turing-Grade und fragte, ob es einen re-Grad streng zwischen 0 und 0′ gibt . Das Problem, einen solchen Abschluss zu konstruieren (oder zu zeigen, dass keiner existiert) wurde als Post-Problem bekannt . Dieses Problem wurde in den 1950er Jahren unabhängig von Friedberg und Muchnik gelöst , die zeigten, dass es diese Zwischenabschlüsse gibt. Ihre Beweise entwickelten jeweils die gleiche neue Methode zur Konstruktion von Wiederabschlüssen, die als Prioritätsmethode bekannt wurde . Die Prioritätsmethode ist jetzt die Hauptmethode zum Festlegen von Ergebnissen über Zurücksetzungen.

Die Idee des Prioritätsverfahrens zum Konstruieren eines Resets X besteht darin, eine abzählbare Folge von Anforderungen aufzulisten , die X erfüllen muss. Um beispielsweise einen Reset X zwischen 0 und 0′ zu konstruieren, genügt es, die Anforderungen A _e und B _e für jede natürliche Zahl e zu erfüllen , wobei A _e erfordert, dass die Orakelmaschine mit Index e nicht 0′ aus X . berechnet und B _e erfordert, dass die Turing-Maschine mit Index e (und kein Orakel) X nicht berechnet . Diese Anforderungen werden in eine Prioritätsreihenfolge gebracht , die eine explizite Bijektion der Anforderungen und der natürlichen Zahlen ist. Der Beweis erfolgt induktiv mit einer Stufe für jede natürliche Zahl; diese Stadien kann man sich als Zeitschritte vorstellen, in denen die Menge X aufgezählt wird. In jeder Phase können Zahlen in X eingefügt oder für immer daran gehindert werden, X einzugeben, um die Anforderungen zu erfüllen (dh sie zwingen, zu bleiben , sobald X vollständig aufgezählt wurde). Manchmal kann eine Zahl in X aufgezählt werden , um eine Anforderung zu erfüllen, aber dies würde dazu führen, dass eine zuvor erfüllte Anforderung nicht erfüllt (d. h. verletzt wird ). Die Prioritätsreihenfolge der Anforderungen wird verwendet, um zu bestimmen, welche Anforderung in diesem Fall zu erfüllen ist. Die informelle Idee ist, dass, wenn eine Anforderung verletzt wird, sie schließlich aufhört, verletzt zu werden, nachdem alle Anforderungen mit höherer Priorität nicht mehr verletzt wurden, obwohl nicht jedes Prioritätsargument diese Eigenschaft hat. Es muss argumentiert werden, dass die Gesamtmenge X re ist und alle Anforderungen erfüllt. Prioritätsargumente können verwendet werden, um viele Fakten über Zurücksetzungen zu beweisen; die verwendeten Anforderungen und die Art und Weise, wie sie erfüllt werden, müssen sorgfältig ausgewählt werden, um das gewünschte Ergebnis zu erzielen.

Siehe auch

• Martin messen

Verweise

Monographien (Grundstudium)

• Cooper, SB Berechenbarkeitstheorie . Chapman & Hall/CRC, Boca Raton, FL, 2004. ISBN  1-58488-237-9
• Cutland, N. Berechenbarkeit. Cambridge University Press, Cambridge-New York, 1980. ISBN  0-521-22384-9 ; ISBN  0-521-29465-7

Monographien und Übersichtsartikel (Absolventenstufe)

• Ambos-Spies, K. und Fejer, P. Grade der Unlösbarkeit. Unveröffentlicht. http://www.cs.umb.edu/~fejer/articles/History_of_Degrees.pdf
• Lerman, M. Grade der Unlösbarkeit. Perspektiven in der mathematischen Logik. Springer-Verlag, Berlin, 1983. ISBN  3-540-12155-2
• Odifreddi, PG (1989), Classical Recursion Theory , Studies in Logic and the Foundations of Mathematics, 125 , Amsterdam: North-Holland, ISBN 978-0-444-87295-1, HERR  0982269
• Odifreddi, PG (1999), Klassische Rekursionstheorie. vol. II , Studies in Logic and the Foundations of Mathematics, 143 , Amsterdam: Nordholland, ISBN 978-0-444-50205-6, HERR  1718169
• Rogers, H. Die Theorie der rekursiven Funktionen und der effektiven Berechenbarkeit , MIT Press. ISBN  0-262-68052-1 , ISBN  0-07-053522-1
• Sacks, Gerald E. Grade der Unlösbarkeit (Annals of Mathematics Studies), Princeton University Press. ISBN  978-0-6910-7941-7
• Simpson, S. Grade der Unlösbarkeit: eine Übersicht über die Ergebnisse. Handbook of Mathematical Logic , North-Holland, 1977, S. 631–652.
• Shoenfield, Joseph R. Grade der Unlösbarkeit , Nordholland/Elsevier, ISBN  978-0-7204-2061-6 .
• Shore, R. (1993). „Die Theorien der T-, tt- und wtt-re-Grade: Unentscheidbarkeit und darüber hinaus“. In Univ. Nak. del Sur, Bahía Blanca (Hrsg.). Proceedings of the IX Latin American Symposium on Mathematical Logic, Teil 1 (Bahía Blanca, 1992) . Notas Lógica Mat.-Nr. 38 . S. 61–70.
• Soare, R. Rekursiv aufzählbare Mengen und Grade. Perspektiven in der mathematischen Logik. Springer-Verlag, Berlin, 1987. ISBN  3-540-15299-7
• Soare, Robert I. Rekursiv aufzählbare Mengen und Grade. Stier. Amer. Mathematik. Soz. 84 (1978), Nr. 6, 1149–1181. MR 508451

Forschungsunterlagen

• Kleene, Stephen Cole ; Post, Emil L. (1954), "The Upper Semi-Gitter of Degrees of Recursive Unsolvability", Annals of Mathematics , Second Series, 59 (3): 379–407, doi : 10.2307/1969708 , ISSN  0003-486X , JSTOR  1969708 , MR  0061078
• Lachlan, AH (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, AH (1966b), "Die Unmöglichkeit, relative Komplemente für rekursiv aufzählbare Grade zu finden", J. Symb. Protokoll. , 31 (3): 434–454, doi : 10.2307/2270459 , JSTOR  2270459 .
• Lachlan, AH; Soare, RI (1980), "Nicht jedes endliche Gitter ist in die rekursiv aufzählbaren Grade einbettbar", Advances in Mathematics , 37 : 78–82, doi : 10.1016/0001-8708(80)90027-4 .
• Nies, André; Ufer, Richard A.; Slaman, Theodore A. (1998), "Interpretability and definability in the recursively enumerable degree", Proceedings of the London Mathematical Society , 77 (2): 241–291, CiteSeerX  10.1.1.29.9588 , doi : 10.1112/S002461159800046X , ISSN  0024-6115 , HERR  1635141
• Post, Emil L. (1944), "Recursively enumerable sets of positive integers and their Decision Probleme", Bulletin of the American Mathematical Society , 50 (5): 284–316, doi : 10.1090/S0002-9904-1944-08111- 1 , ISSN  0002-9904 , MR  0010514
• Sacks, GE (1964), "Die rekursiv aufzählbaren Grade sind dicht", Annals of Mathematics , Second Series, 80 (2): 300–312, doi : 10.2307/1970393 , JSTOR  1970393 .
• Ufer, 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. (1977), "Theorie erster Ordnung der Grade der rekursiven Unlösbarkeit", Annals of Mathematics , Second Series, 105 (1): 121–139, doi : 10.2307/1971028 , ISSN  0003-486X , JSTOR  197128 , HERR  0432435
• Thomason, SK (1971), "Untergitter der rekursiv aufzählbaren Grade", Z. Math. Logik Grundlag. Mathematik. , 17 : 273–280, doi : 10.1002/malq.19710170131 .
• Yates, CEM (1966), "A minimal pair of recursively enumerable degree ", Journal of Symbolic Logic , 31 (2): 159–168, doi : 10.2307/2269807 , JSTOR  2269807 .