Quelltext der Seite Turinggrad

In der [[Berechenbarkeitstheorie]] und der [[Mathematische Logik|mathematischen Logik]] misst der '''Turinggrad''' (auch '''Grad der Unlösbarkeit''') einer Menge [[Natürliche Zahl|natürlicher Zahlen]] die [[Algorithmus|algorithmische]] Unlösbarkeit der Menge. Das Konzept des Turinggrades ist fundamental in der Berechenbarkeitstheorie, wo Mengen natürlicher Zahlen oft als [[Entscheidungsproblem]]e angesehen werden; der Turinggrad einer Menge gibt an, wie schwer das Entscheidungsproblem für die Menge ist.

Zwei Mengen sind ''Turing-äquivalent'', wenn sie den gleichen Grad der Unlösbarkeit haben; jeder Turinggrad ist eine Menge Turing-äquivalenter Mengen, sodass zwei Mengen genau dann in unterschiedlichen Turinggraden liegen, wenn sie nicht Turing-äquivalent sind. Außerdem sind die Turinggrade im folgenden Sinne [[Partielle Ordnung|partiell geordnet]]: Wenn der Turinggrad einer Menge <math>X</math> kleiner als der Turinggrad einer Menge <math>Y</math> ist, dann kann jede (unberechenbare) Prozedur, die korrekt entscheidet, ob Zahlen in <math>Y</math> liegen, berechenbar in eine Prozedur umgewandelt werden, die korrekt entscheidet, ob Zahlen in <math>X</math> liegen. In diesem Sinne korrespondiert der Turinggrad einer Menge mit dem Grad ihrer algorithmischen Unlösbarkeit.

Die Turinggrade wurden 1944 von [[Emil Leon Post]] eingeführt, und viele grundlegende Resultate wurden 1954 von [[Stephen Cole Kleene]] und Post bewiesen. Die Turinggrade sind bis heute Gegenstand intensiver Forschung. Viele Beweise in diesem Gebiet benutzen eine Beweistechnik, die als Prioritätsmethode bekannt ist.

== Turing-Äquivalenz ==

Im Folgenden bezieht sich das Wort ''Menge'' auf Teilmengen natürlicher Zahlen. Eine Menge <math>X</math> heißt [[Reduktion (Theoretische Informatik)#Reduktionen in der Berechenbarkeitstheorie|Turing-reduzierbar]] auf eine Menge <math>Y</math>, wenn es eine [[Orakel-Turingmaschine]] gibt, die mit Hilfe eines Orakels für <math>Y</math> entscheidet, ob eine gegebene Zahl in <math>X</math> liegt. Die Notation <math>X \le_T Y</math> steht für: <math>X</math> ist auf <math>Y</math> Turing-reduzierbar.

Zwei Mengen <math>X</math> und <math>Y</math> heißen Turing-äquivalent, wenn sie aufeinander Turing-reduzierbar sind. Die Notation <math>X\equiv_T Y</math> steht für: <math>X</math> und <math>Y</math> sind Turing-äquivalent. Die Relation <math>\equiv_T</math> ist eine [[Äquivalenzrelation]].

== Turinggrad ==

Ein Turinggrad ist eine [[Äquivalenzklasse]] der Relation <math>\equiv_T</math>. Die Notation <math>[X]</math> bezeichnet die Äquivalenzklasse, die die Menge <math>X</math> enthält. Die Klasse aller Turinggrade wird mit <math>\mathcal{D}</math> bezeichnet.

Die Turinggrade haben eine [[partielle Ordnung]] <math>\le</math>. Sie ist so definiert, dass <math>[X] \le [Y]</math> genau dann gilt, wenn <math>X \le_T Y</math>. Es gibt einen Turinggrad, der genau die [[Entscheidbare Menge|entscheidbaren]] Mengen enthält, und dieser Grad ist kleiner als alle anderen. Er wird mit <math>\mathbf 0</math> (Null) bezeichnet, da er das kleinste Element der partiell geordneten Menge <math>\mathcal{D}</math> ist. Turinggrade werden meist durch Fettdruck bezeichnet, um sie von Mengen zu unterscheiden. Als Variablen für Turinggrade dienen fette kleine Buchstaben <math>\mathbf a, \mathbf b</math> etc.

Für alle Mengen <math>X</math> und <math>Y</math> ist <math>X \oplus Y</math> (gesprochen ''join'') die Vereinigung der Mengen <math>\left\{2 n \mid n \in X\right\}</math> und <math>\left\{2 n + 1\mid n \in Y\right\}</math>. Der Turinggrad von <math>X \oplus Y</math> ist das [[Supremum]] der Grade <math>[X]</math> und <math>[Y]</math>. Damit ist <math>\mathcal{D}</math> ein oberer [[Halbverband]]. Das Supremum der Grade <math>\mathbf a</math> und <math>\mathbf b</math> wird mit <math>\mathbf a \cup \mathbf b</math> bezeichnet. Es ist bekannt, dass <math>\mathcal{D}</math> kein [[Verband (Mathematik)|Verband]] ist, da es Paare von Graden ohne Infimum gibt.

Für jede Menge <math>X</math> bezeichnet <math>X^\prime</math> die Menge der Indizes von Orakelmaschinen, die auf ihrem eigenen Index als Eingabe halten, wenn sie <math>X</math> als Orakel benutzen. Die Menge <math>X^\prime</math> wird als ''[[Turing-Sprungoperator|Turing-Sprung]]'' von <math>X</math> bezeichnet.  Der Turing-Sprung eines Grades <math>[X]</math> ist der Grad <math>\left[X^\prime\right]</math>; dies ist [[Wohldefiniertheit|wohldefiniert]], da <math>X^\prime \equiv_TY^\prime</math> aus <math>X \equiv_T Y</math> folgt. Ein wichtiges Beispiel ist <math>\mathbf 0^\prime</math>, der Grad des [[Halteproblem]]s.

== Grundlegende Eigenschaften der Turinggrade ==

* Jeder Turinggrad ist [[abzählbar unendlich]], das heißt, er enthält genau <math>\aleph_0</math> Mengen.

* Es gibt <math>\beth_1</math> (siehe [[Beth-Funktion]]) verschiedene Turinggrade.

* Für jeden Grad <math>\mathbf a</math> gilt die strikte Ungleichung <math>\mathbf a < \mathbf a^\prime</math>.

* Für jeden Grad <math>\mathbf a</math> ist die Menge der Grade unter <math>\mathbf a</math> [[abzählbare Menge|höchstens abzählbar]]. Die Menge der Grade über <math>\mathbf a</math> hat Mächtigkeit <math>\beth_1</math>.

== Struktur der Turinggrade ==

Die Struktur der Turinggrade wurde intensiv erforscht. Die folgende Liste gibt nur wenige der vielen bekannten Ergebnisse an. Generell lässt sich aus den bekannten Ergebnissen schließen, dass die Struktur der Turinggrade sehr kompliziert ist.

=== Ordnungseigenschaften ===

* Es gibt minimale Grade.  Ein Grad <math>\mathbf a</math> heißt minimal, wenn <math>\mathbf a</math> ungleich <math>\mathbf 0</math> ist und es keinen Grad zwischen <math>\mathbf 0</math> und <math>\mathbf a</math> gibt. Damit ist die Ordnung der Grade nicht [[Dichte Ordnung|dicht]].

* Für jeden Grad <math>\mathbf a</math> ungleich <math>\mathbf 0</math> gibt es einen Grad <math>\mathbf b</math>, der mit <math>\mathbf a</math> nicht vergleichbar ist.

* Es gibt <math>\beth_1</math> untereinander nicht vergleichbare Turinggrade.

* Es gibt Paare von Graden ohne Infimum. Damit ist <math>\mathcal{D}</math> kein Verband.

* Jede abzählbare partielle Ordnung lässt sich in die Turinggrade einbetten.

* Keine unendliche, strikt aufsteigende Folge von Graden hat ein Supremum.

=== Eigenschaften des Sprungoperators ===

* Für jeden Grad <math>\mathbf a</math> gibt es einen Grad zwischen <math>\mathbf a</math> und <math>\mathbf a^\prime</math>. Es gibt sogar eine abzählbar unendliche Folge paarweise nicht vergleichbarer Grade zwischen <math>\mathbf a</math> und <math>\mathbf a^\prime</math>.

* Ein Grad <math>\mathbf a</math> hat die Form <math>\mathbf b^\prime</math> für ein <math>\mathbf b</math> genau dann, wenn <math>\mathbf 0 < \mathbf a</math> gilt.

* Für jeden Grad <math>\mathbf a</math> gibt es einen Grad <math>\mathbf b</math>, sodass <math>\mathbf a < \mathbf b</math> und <math>\mathbf a^\prime = \mathbf b^\prime</math>. Solch ein Grad <math>\mathbf b</math> heißt niedrig relativ zu <math>\mathbf a</math>.

* Es gibt eine unendliche Folge <math>\left(\mathbf a_i\right)_i</math> von Graden, sodass <math>\mathbf a_{i+1}^\prime \le \mathbf a_i</math> für alle <math>i</math>.

=== Logische Eigenschaften ===

* Simpson (1977) zeigte, dass die Theorie von <math>\mathcal{D}</math> in der [[Prädikatenlogik erster Stufe]] in der Sprache <math>\left\langle{\le},{=}\right\rangle</math> oder <math>\left\langle{\le},{\cdot}^\prime,{=}\right\rangle</math> [[Many-one-Reduktion|many-one-äquivalent]] zur Theorie der natürlichen Zahlen in der [[Prädikatenlogik zweiter Stufe]] ist.

* Shore und Slaman (1999) zeigten, dass sich der Sprungoperator in der Struktur der Grade in der Logik erster Stufe mit der Sprache <math>\left\langle{\le},{=}\right\rangle</math> definieren lässt.

== Struktur der rekursiv aufzählbaren Turinggrade ==
[[Datei:Rehasse.png|mini|Dieser endliche Verband kann nicht in die rekursiv aufzählbaren Grade eingebettet werden.]]
Ein Grad heißt rekursiv aufzählbar, wenn er eine [[rekursiv aufzählbare Menge]] enthält. Jeder rekursiv aufzählbare Grad ist kleiner oder gleich <math>\mathbf 0^\prime</math>, aber nicht jeder Grad kleiner <math>\mathbf 0^\prime</math> ist rekursiv aufzählbar.

* ([[Satz von Friedberg und Muchnik]], 1956) Es gibt rekursiv aufzählbare Grade zwischen <math>\mathbf 0</math> und <math>\mathbf 0^\prime</math>.

* ([[Gerald Sacks|G. E. Sacks]], 1964) Die rekursiv aufzählbaren Grade sind dicht, das heißt, zwischen zwei rekursiv aufzählbaren Graden existiert immer ein dritter rekursiv aufzählbarer Grad.

* (A. H. Lachlan, 1966a und C. E. M. Yates, 1966) Es gibt zwei rekursiv aufzählbare Grade, die kein Infimum in den rekursiv aufzählbaren Graden haben.

* (A. H. Lachlan, 1966a und C. E. M. Yates, 1966) Es gibt ein Paar von rekursiv aufzählbaren Graden ungleich <math>\mathbf 0</math>, deren Infimum <math>\mathbf 0</math> ist.

* (S. K. Thomason, 1971) Jeder endlicher distributiver Verband kann in die rekursiv aufzählbaren Grade eingebettet werden. Es ist sogar möglich, die abzählbare [[boolesche Algebra]] ohne Atome so einzubetten, dass Suprema und Infima erhalten bleiben.

* (A. H. Lachlan und [[Robert I. Soare|R. I. Soare]], 1980) Nicht alle endlichen Verbände können in die rekursiv aufzählbaren Grade eingebettet werden, sodass Suprema und Infima erhalten bleiben. So kann insbesondere der rechts abgebildete Verband nicht eingebettet werden.

* (A. H. Lachlan, 1966b) Es gibt kein Paar rekursiv aufzählbarer Grade, deren Infimum <math>\mathbf 0</math> ist und deren Supremum <math>\mathbf 0^\prime</math> ist,

* ([[Leo Harrington|L. A. Harrington]] und [[Theodore Slaman|T. A. Slaman]], siehe Nies, Shore und Slaman (1998)) Die Theorie der rekursiv aufzählbaren Grade in der Sprache <math>\left\langle\mathbf 0,{\le},{=}\right\rangle</math> in Logik erster Stufe ist many-one-äquivalent zur Theorie der Arithmetik in Logik erster Stufe.

== Literatur ==

=== Einführungen ===
* S. B. Cooper: ''Computability Theory.'' Chapman & Hall/CRC,  2004, ISBN 1-58488-237-9.
* Nigel Cutland: ''Computability, An introduction to recursive function theory.'' Cambridge University Press, 1980, ISBN 0-521-29465-7.
* Klaus Heidler, Hans Hermes, Friedrich-K. Mahn.: ''Rekursive Funktionen.'' Mannheim – Wien – Zürich 1977.
* [[Hans Hermes]]: ''Aufzählbarkeit – Entscheidbarkeit – Berechenbarkeit. Einführung in die Theorie der rekursiven Funktionen''. Berlin / Göttingen / Heidelberg 1961. (2. Auflage. 1971, als Heidelberger Taschenbuch).
* [[Stephen Kleene]]: ''Introduction to Metamathematics.'' North-Holland, 1952, ISBN 0-7204-2103-9.
* {{cite book|author = [[Michael Sipser]] | year = 1997 | title = Introduction to the Theory of Computation | publisher = PWS Publishing | isbn = 0-534-94728-X |language=en}} Part Two: Computability Theory, Chapters 3–6, S.&nbsp;123–222.

=== Spezialwerke ===
* [[Piergiorgio Odifreddi]]: ''Classical Recursion Theory''. North-Holland 1989, ISBN 0-444-87295-7.
* P. Odifreddi: ''Classical Recursion Theory, Volume II.'' Elsevier, 1999, ISBN 0-444-50205-X.
* {{Literatur |Autor=Hartley Rogers |Titel=Theory of recursive functions and effective computability |Verlag=McGraw-Hill |Datum=1967}}
* G. Sacks: ''Higher Recursion Theory.'' Springer-Verlag, 1990, ISBN 3-540-19305-7.
* R. I. Soare: ''Recursively Enumerable Sets and Degrees.'' Perspectives in Mathematical Logic. Springer-Verlag, 1987, ISBN 0-387-15299-7.

=== Forschungspapiere ===
* {{Literatur
   |Autor=Stephen Cole Kleene, Emil L. Post
   |Titel=The upper semi-lattice of degrees of recursive unsolvability
   |Sammelwerk=[[Annals of Mathematics|Annals of Mathematics. Second Series]]
   |Band=59
   |Nummer=3
   |Datum=1954
   |ISSN=0003-486X
   |Seiten=379–407
   |DOI=10.2307/1969708
   |JSTOR=1969708}}
* {{Literatur
   |Autor=A.H. Lachlan
   |Titel=Lower Bounds for Pairs of Recursively Enumerable Degrees
   |Sammelwerk=Proceedings of the London Mathematical Society
   |Band=3
   |Nummer=1
   |Datum=1966
   |Seiten=537}}
* {{Literatur
   |Autor=A.H. Lachlan
   |Titel=The impossibility of finding relative complements for recursively enumerable degrees
   |Sammelwerk=J. Symb. Logic
   |Band=31
   |Nummer=3
   |Datum=1966
   |Seiten=434–454
   |DOI=10.2307/2270459
   |JSTOR=2270459}}
* {{Literatur
   |Autor=A.H. Lachlan, R.I. Soare
   |Titel=Not every finite lattice is embeddable in the recursively enumerable degrees
   |Sammelwerk=Advances in Math
   |Band=37
   |Datum=1980
   |Seiten=78–82
   |DOI=10.1016/0001-8708(80)90027-4}}
* {{Literatur
   |Autor=André Nies, Richard A. Shore, Theodore A. Slaman
   |Titel=Interpretability and definability in the recursively enumerable degrees
   |Sammelwerk=Proc. London Math. Soc. (3)
   |Band=77
   |Nummer=2
   |Datum=1998
   |ISSN=0024-6115
   |Seiten=241–291
   |DOI=10.1112/S002461159800046X}}
* {{Literatur
   |Autor=Emil L. Post
   |Titel=Recursively enumerable sets of positive integers and their decision problems
   |Sammelwerk=[[Bulletin of the American Mathematical Society]]
   |Band=50
   |Nummer=5
   |Datum=1944
   |ISSN=0002-9904
   |Seiten=284–316
   |DOI=10.1090/S0002-9904-1944-08111-1}}
* {{Literatur
   |Autor=[[Gerald Sacks]]
   |Titel=The recursively enumerable degrees are dense
   |Sammelwerk=Ann. Of Math.(2)
   |Band=80
   |Nummer=2
   |Datum=1964
   |Seiten=300–312
   |DOI=10.2307/1970393
   |JSTOR=1970393}}
* {{Literatur
   |Autor=Richard A. Shore, Theodore A. Slaman
   |Titel=Defining the Turing jump
   |Sammelwerk=Mathematical Research Letters
   |Band=6
   |Datum=1999
   |ISSN=1073-2780
   |Seiten=711–722}}
* {{Literatur
   |Autor=Stephen G. Simpson
   |Titel=First-order theory of the degrees of recursive unsolvability
   |Sammelwerk=[[Annals of Mathematics|Annals of Mathematics. Second Series]]
   |Band=105
   |Nummer=1
   |Datum=1977
   |ISSN=0003-486X
   |Seiten=121–139
   |DOI=10.2307/1971028
   |JSTOR=1971028}}
* {{Literatur
   |Autor=Thomason, S.K.
   |Titel=Sublattices of the recursively enumerable degrees
   |Sammelwerk=Z. Math. Logik Grundlagen Math
   |Band=17
   |Datum=1971
   |Seiten=273–280
   |DOI=10.1002/malq.19710170131}}
* {{Literatur
   |Autor=C.E.M. Yates
   |Titel=A minimal pair of recursively enumerable degrees
   |Sammelwerk=J. Symbolic Logic
   |Band=31
   |Nummer=2
   |Datum=1966
   |Seiten=159–168
   |DOI=10.2307/2269807
   |JSTOR=2269807}}

[[Kategorie:Berechenbarkeitstheorie| ]]
[[Kategorie:Mathematische Logik]]