Turinggrad

Im Folgenden bezieht sich das Wort Menge auf Teilmengen natürlicher Zahlen. Eine Menge ${\displaystyle X}$ heißt Turing-reduzierbar auf eine Menge ${\displaystyle Y}$, wenn es eine Orakel-Turingmaschine gibt, die mit Hilfe eines Orakels für ${\displaystyle Y}$ entscheidet, ob eine gegebene Zahl in ${\displaystyle X}$ liegt. Die Notation ${\displaystyle X\leq _{T}Y}$ steht für: ${\displaystyle X}$ ist auf ${\displaystyle Y}$ Turing-reduzierbar.

Zwei Mengen ${\displaystyle X}$ und ${\displaystyle Y}$ heißen Turing-äquivalent, wenn sie aufeinander Turing-reduzierbar sind. Die Notation ${\displaystyle X\equiv _{T}Y}$ steht für: ${\displaystyle X}$ und ${\displaystyle Y}$ sind Turing-äquivalent. Die Relation ${\displaystyle \equiv _{T}}$ ist eine Äquivalenzrelation.

Ein Turinggrad ist eine Äquivalenzklasse der Relation ${\displaystyle \equiv _{T}}$. Die Notation ${\displaystyle [X]}$ bezeichnet die Äquivalenzklasse, die die Menge ${\displaystyle X}$ enthält. Die Klasse aller Turinggrade wird mit ${\displaystyle {\mathcal {D}}}$ bezeichnet.

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

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

Für jede Menge ${\displaystyle X}$ bezeichnet ${\displaystyle X^{\prime }}$ die Menge der Indizes von Orakelmaschinen, die auf ihrem eigenen Index als Eingabe halten, wenn sie ${\displaystyle X}$ als Orakel benutzen. Die Menge ${\displaystyle X^{\prime }}$ wird als Turing-Sprung von ${\displaystyle X}$ bezeichnet. Der Turing-Sprung eines Grades ${\displaystyle [X]}$ ist der Grad ${\displaystyle \left[X^{\prime }\right]}$; dies ist wohldefiniert, da ${\displaystyle X^{\prime }\equiv _{T}Y^{\prime }}$ aus ${\displaystyle X\equiv _{T}Y}$ folgt. Ein wichtiges Beispiel ist ${\displaystyle \mathbf {0} ^{\prime }}$, der Grad des Halteproblems.

• Jeder Turinggrad ist abzählbar unendlich, das heißt, er enthält genau ${\displaystyle \aleph _{0}}$ Mengen.

• Es gibt ${\displaystyle \beth _{1}}$ (siehe Beth-Funktion) verschiedene Turinggrade.

• Für jeden Grad ${\displaystyle \mathbf {a} }$ gilt die strikte Ungleichung ${\displaystyle \mathbf {a} <\mathbf {a} ^{\prime }}$.

• Für jeden Grad ${\displaystyle \mathbf {a} }$ ist die Menge der Grade unter ${\displaystyle \mathbf {a} }$ höchstens abzählbar. Die Menge der Grade über ${\displaystyle \mathbf {a} }$ hat Mächtigkeit ${\displaystyle \beth _{1}}$.

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.

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 ${\displaystyle \mathbf {0} ^{\prime }}$, aber nicht jeder Grad kleiner ${\displaystyle \mathbf {0} ^{\prime }}$ ist rekursiv aufzählbar.

• (Satz von Friedberg und Muchnik, 1956) Es gibt rekursiv aufzählbare Grade zwischen ${\displaystyle \mathbf {0} }$ und ${\displaystyle \mathbf {0} ^{\prime }}$.

• (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 and 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 and C. E. M. Yates, 1966) Es gibt ein Paar von rekursiv aufzählbaren Graden ungleich ${\displaystyle \mathbf {0} }$, deren Infimum ${\displaystyle \mathbf {0} }$ 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 and 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 ${\displaystyle \mathbf {0} }$ ist und deren Supremum ${\displaystyle \mathbf {0} ^{\prime }}$ ist,

• (L. A. Harrington and T. A. Slaman, siehe Nies, Shore, and Slaman (1998)) Die Theorie der rekursiv aufzählbaren Grade in der Sprache ${\displaystyle \left\langle \mathbf {0} ,{\leq },{=}\right\rangle }$ in Logik erster Stufe ist many-one-äquivalent zur Theorie der Arithmetik in Logik erster Stufe.