Satz von Friedberg und Muchnik

Der Satz von Friedberg und Muchnik ist ein Ergebnis der Berechenbarkeitstheorie und mathematischen Logik, das 1956/1957 unabhängig voneinander von Richard M. Friedberg und Albert Muchnik bewiesen wurde. Es besagt, dass es rekursiv aufzählbare Turinggrade gibt, die zwischen 0 und 0′ liegen. Damit gibt es also rekursiv aufzählbare Mengen, die nicht entscheidbar sind, aber im Sinne der Turingreduktion leichter als das Halteproblem. Für ihre Beweise entwickelten Friedberg und Muchnik eine neue Beweistechnik, die als Prioritätsmethode oder Prioritätsargument bekannt ist und die zu einer wichtigen Technik in der Berechenbarkeitstheorie wurde.

Geschichte

Emil Post untersuchte in einer Arbeit von 1944 die Turinggrade und fragte, ob es rekursiv aufzählbare Turinggrade zwischen 0 und 0′ gibt. Diese Frage wurde als Postsches Problem bekannt. Post definierte die einfachen Mengen und konnte zeigen, dass diese unter der many-one-Reduktion strikt zwischen den entscheidbaren Mengen und dem Halteproblem liegen, ohne dies auch für die stärkere Turingreduktion zeigen zu können. J.C.E. Dekker zeigte 1954, dass dies unmöglich ist, da es einfache Mengen in 0′ gibt. Das Problem wurde 1956/57 unabhängig voneinander von Friedberg und Muchnik durch die neu entwickelte Prioritätsmethode gelöst. 1986 veröffentlichte Antonín Kučera eine neue Lösung, die kein Prioritätsargument benötigt.

Beweis

Idee

Der folgende Beweis folgt der Darstellung von Cooper 2004 und beruht auf den ursprünglichen Beweisen von Friedberg und Muchnik.

Es werden simultan zwei rekursiv aufzählbare Mengen $A$ und $B$ konstruiert, die aufeinander jeweils nicht Turing-reduzierbar sind: $A\not \leq _{T}B$ und $B\not \leq _{T}A$. Wenn diese Bedingungen erfüllt sind, folgt direkt die Aussage des Satzes. Denn wenn $A$ oder $B$ entscheidbar wäre, ließe es sich auf die andere Menge Turing-reduzieren, und da alle rekursiv aufzählbaren Mengen auf das Halteproblem Turing-reduzierbar sind, können A und B auch nicht in 0′ liegen.

Diese Anforderungen werden durch eine unendliche Liste von Anforderungen sichergestellt. Sei $\Phi _{0},\Phi _{1},\dotsc$ eine berechenbare Aufzählung der Orakel-Turingmaschinen. Dann gibt es für jede Maschine $\Phi _{i}$ zwei Anforderungen:

• $R_{2i}$: $\Phi _{i}$ beschreibt keine Turingreduktion von $A$ auf $B$. Formal: $A\neq \Phi _{i}^{B}$

• $R_{2i+1}$: $\Phi _{i}$ beschreibt keine Turingreduktion von $B$ auf $A$. Formal: $B\neq \Phi _{i}^{A}$

Wenn alle $R_{2i}$ erfüllt sind, gibt es keine Turingreduktion von $A$ auf $B$ und es gilt $A\not \leq _{T}B$. Analog gilt $B\not \leq _{T}A$, wenn alle $R_{2i+1}$ erfüllt sind.

Die Anforderungen sind nach ihrer Priorität geordnet, sodass $R_{0}$ höchste Priorität hat, $R_{1}$ zweithöchste etc.

Es werden berechenbare Folgen endlicher Mengen $A_{0}\subseteq A_{1}\subseteq A_{2}\subseteq \dotsb$ und $B_{0}\subseteq B_{1}\subseteq B_{2}\subseteq \dotsb$ konstruiert. A und B sind dann die unendlichen Vereinigungen dieser Folgen: $A=\bigcup _{i\in \mathbb {N} }A_{i}$ und $B=\bigcup _{i\in \mathbb {N} }B_{i}$. Da die Folgen berechenbar sind, sind ihre Vereinigungen $A$ und $B$ rekursiv aufzählbar.

Es ist $A_{0}=B_{0}=\emptyset$. Im $s+1$-ten Schritt der Konstruktion werden aus $A_{s}$ und $B_{s}$ die Mengen $A_{s+1}\supseteq A_{s}$ und $B_{s+1}\supseteq B_{s}$ konstruiert. Die Konstruktion wird von Strategien übernommen. Jede der Anforderungen hat eine Strategie, die versucht, diese Anforderung zu erfüllen.

Strategien

Intuition

Jede Strategie $R_{2i}$ muss erzwingen, dass eine Ungleichung $A\neq \Phi _{i}^{B}$ gilt. Hierzu gibt es zwei Möglichkeiten: entweder die Strategie fügt einen Zeugen $x$ zu $A$ hinzu, der nicht in $\Phi _{i}^{B}$ liegt, oder sie erzwingt, dass es einen Zeugen $x$ gibt, der in $\Phi _{i}^{B}$ liegt und nie nach $A$ gelangt. Dabei gibt es zwei Schwierigkeiten. Zum einen ist $\Phi _{i}^{B}$ nicht immer eine totale Funktion und die Frage $\Phi _{i}^{B}(x)$ ist daher unentscheidbar. Dies wird dadurch gelöst, dass die Strategie im $s$-ten Schritt der Konstruktion nur die ersten $s$ Schritte der Berechnung von $\Phi _{i}^{B}(x)$ durchführt. Wenn $\Phi _{i}^{B}(x)$ nach $t$ Schritten hält, dann wird die Strategie den Wert von $\Phi _{i}^{B}(x)$ im $t$-ten Schritt der Konstruktion erfahren und kann entsprechend bestimmen, ob $x$ nach $A$ gelangt oder nicht. Hält $\Phi _{i}^{B}(x)$ nicht, dann beschreibt $\Phi _{i}$ keine totale Funktion und somit keine Turingreduktion. Damit ist $R_{2i}$ automatisch erfüllt.

Zum anderen ist $B$ während der Konstruktion von $A$ noch nicht vorhanden, da beide Mengen simultan konstruiert werden. Daher erhält die Orakelmaschine $\Phi _{i}$ als Orakel im $s$-ten Schritt statt $B$ die endliche Menge $B_{s}$. Eine Orakelturingmaschine kann, falls sie hält, nur endlich viele Orakelanfragen stellen. Damit genügt es, zu fordern, dass alle späteren Mengen $B_{t}$ auf allen Zahlen $x\leq k$ ($k$ ist größte Orakelanfrage in der Berechnung von $\Phi _{i}^{B}(x)$) mit $B_{s}$ übereinstimmen, um zu gewährleisten, dass $\Phi _{i}^{B_{s}}(x)=\Phi _{i}^{B}(x)$ ist. Die Strategie setzt daher $k$ als $B$-Beschränkung fest, das heißt keine Strategie $R_{2i+1}$ darf zukünftig Zahlen $x\leq k$ zu $B$ hinzufügen.

Die Strategien $R_{2i+1}$ arbeiten vollkommen analog, mit vertauschten Rollen von $A$ und $B$. Diese Strategien können also analog $A$-Beschränkungen einführen, welche die $R_{2i}$-Strategien in der Wahl der Zeugen beschränken. Eine Beschränkung kann nun aber auch den Zeugen einer bereits aktiven Strategie unbrauchbar machen, wenn dieser kleiner als $k$ ist. Die Lösung ist, dass jede Strategie nur diejenigen Beschränkungen beachtet, die von einer Strategie höherer Priorität aufgestellt wurden. Erkennt eine Strategie, dass sie verletzt wurde, das heißt, dass eine von ihr aufgestellte Beschränkung von einer Strategie höherer Priorität verletzt wurde, wählt sie einen neuen Zeugen und beginnt von vorne.

Nun lässt sich wie folgt induktiv zeigen, dass jede Strategie nur endlich viele Male verletzt wird, also irgendwann endgültig erfüllt wird. Da $R_{0}$ höchste Priorität hat, wird es nie verletzt. Da es für jedes $R_{s+1}$ nur endlich viele Anforderungen mit höherer Priorität gibt, die alle nach Induktionsvoraussetzung nur endlich oft verletzt werden, wird $R_{s+1}$ ebenfalls nur endlich oft verletzt, da es nur von Strategien mit höherer Priorität verletzt werden kann.

Formalisierung

Jede Anforderung der Form $R_{2i}$ hat eine Strategie, die sich wie folgt prozedural darstellen lässt:

1. Wähle einen potentiellen Zeugen x für $A\neq \Phi _{i}^{B}$, wobei x noch nicht in A liegt, über allen A-Beschränkungen mit höherer Priorität liegt und nicht schon als Zeuge gewählt wurde.
2. In jedem späteren Schritt $s$, überprüfe ob eine der folgenden Bedingungen gilt:
   1. x liegt unter einer A-Beschränkung mit höherer Priorität. In diesem Fall wurde $R_{2i}$ verletzt und geht zurück nach (1).
   2. $A_{s}(x)=0=\Phi _{i}^{B_{s}}(x)[s]$. In diesem Fall geht die Strategie nach (3). Dabei ist $\Phi _{i}^{B_{s}}(x)[s]$ das Ergebnis der ersten $s$ Schritte der Berechnung von $\Phi _{i}^{B_{s}}(x)$.
3. $x$ wird zu $A_{s+1}$ hinzugefügt.
4. Sei z die größte Orakelanfrage, die bei der Berechnung von $\Phi _{i}^{B_{s}}(x)$ gestellt wurde. Dann wird die B-Beschränkung z hinzugefügt.
5. In jedem späteren Schritt $s$ wird überprüft, ob x unter einer A-Beschränkung mit höherer Priorität liegt. Wenn ja, geht die Strategie nach (1) zurück.

Die Anforderungen $R_{2i+1}$ haben analoge Strategien, in denen A und B vertauscht sind.

Dabei beginnt die Strategie für die $n$-te Anforderung ihre Aktivität im $n$-ten Schritt der Konstruktion bei (1). In jedem Schritt $s$ sind alle Strategien $R_{k}$ für $k\leq s$ aktiv. Damit müssen in jedem Schritt nur endlich viele Strategien berücksichtigt werden. Da jede Strategie berechenbar ist, ist somit wie gefordert jedes $A_{s}$ und $B_{s}$ berechenbar.

Wie oben gezeigt, wird jede Strategie nur endlich viele Male verletzt. Zudem ist zu zeigen, dass die Anforderung $R_{i}$ erfüllt ist, wenn die zugehörige Strategie nicht mehr verletzt wird. Da jede Strategie $R_{i}$ nur endlich oft verletzt wird und nach (1) zurückgeht, bleiben zwei mögliche Ergebnisse (hier für $R_{2i}$ dargestellt, analog für $R_{2i+1}$):

• $R_{2i}$ wartet unendlich lang bei (2), d. h. $A_{s}(x)=0=\Phi _{i}^{B_{s}}(x)[s]$ wird für kein $s$ erfüllt. Dann ist $\Phi _{i}^{B}(x)$ entweder undefiniert oder gleich 1. Da $x$ nicht in $A$ liegt, ist in beiden Fällen $R_{2i}$ erfüllt.
• $R_{2i}$ erreicht (5), ohne wieder verletzt zu werden. Da $x$ in (3) zu $A$ hinzugefügt wurde, ist $A(x)=1$. Andererseits ist $\Phi _{i}^{B_{s}}(x)=0$. Aufgrund der von $R_{2i}$ hinzugefügten B-Beschränkung hat sich der relevante Teil von $B$ nicht verändert und $\Phi _{i}^{B}(x)=\Phi _{i}^{B_{s}}(x)=0\neq A(x)$.

Analog lässt sich zeigen, dass alle $R_{2i+1}$ erfüllt werden.

Literatur

• S. B. Cooper: Computability Theory. Chapman & Hall/CRC, 2004. ISBN 1-58-488237-9
• Richard M. Friedberg: Two recursively enumerable sets of incomparable degree of unsolvability (solution of Post's problem 1944). In: Proceedings of the National Academy of Sciences. Band 43, S. 236–238 (pnas.org [PDF]). 
• Antonín Kučera: An alternative, priority-free solution to Post's problem. In: Springer Lecture Notes in Computer Science. Band 233, 1986, S. 493–500. 
• A. A. Muchnik: Über die Unlösbarkeit des Problems der Reduzierbarkeit in der Theorie der Algorithmen. (russisch). In: Doklady Akademii Nauk SSSR (N.S.). Band 108, 1956, S. 194–197.