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.[1] 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 ${\displaystyle A}$ und ${\displaystyle B}$ konstruiert, die aufeinander jeweils nicht Turing-reduzierbar sind: ${\displaystyle A\not \leq _{T}B}$ und ${\displaystyle B\not \leq _{T}A}$. Wenn diese Bedingungen erfüllt sind, folgt direkt die Aussage des Satzes. Denn wenn ${\displaystyle A}$ oder ${\displaystyle 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 ${\displaystyle \Phi _{0},\Phi _{1},\dotsc }$ eine berechenbare Aufzählung der Orakel-Turingmaschinen. Dann gibt es für jede Maschine ${\displaystyle \Phi _{i}}$ zwei Anforderungen:

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

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

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

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

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

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

Zum anderen ist ${\displaystyle B}$ während der Konstruktion von ${\displaystyle A}$ noch nicht vorhanden, da beide Mengen simultan konstruiert werden. Daher erhält die Orakelmaschine ${\displaystyle \Phi _{i}}$ als Orakel im ${\displaystyle s}$-ten Schritt statt ${\displaystyle B}$ die endliche Menge ${\displaystyle 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 ${\displaystyle B_{t}}$ auf allen Zahlen ${\displaystyle x\leq k}$ (${\displaystyle k}$ ist größte Orakelanfrage in der Berechnung von ${\displaystyle \Phi _{i}^{B}(x)}$) mit ${\displaystyle B_{s}}$ übereinstimmen, um zu gewährleisten, dass ${\displaystyle \Phi _{i}^{B_{s}}(x)=\Phi _{i}^{B}(x)}$ ist. Die Strategie setzt daher ${\displaystyle k}$ als ${\displaystyle B}$-Beschränkung fest, das heißt keine Strategie ${\displaystyle R_{2i+1}}$ darf zukünftig Zahlen ${\displaystyle x\leq k}$ zu ${\displaystyle B}$ hinzufügen.

Die Strategien ${\displaystyle R_{2i+1}}$ arbeiten vollkommen analog, mit vertauschten Rollen von ${\displaystyle A}$ und ${\displaystyle B}$. Diese Strategien können also analog ${\displaystyle A}$-Beschränkungen einführen, welche die ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle R_{0}}$ höchste Priorität hat, wird es nie verletzt. Da es für jedes ${\displaystyle R_{s+1}}$ nur endlich viele Anforderungen mit höherer Priorität gibt, die alle nach Induktionsvoraussetzung nur endlich oft verletzt werden, wird ${\displaystyle 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 ${\displaystyle R_{2i}}$ hat eine Strategie, die sich wie folgt prozedural darstellen lässt:

1. Wähle einen potentiellen Zeugen x für ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle R_{2i}}$ verletzt und geht zurück nach (1).
   2. ${\displaystyle A_{s}(x)=0=\Phi _{i}^{B_{s}}(x)[s]}$. In diesem Fall geht die Strategie nach (3). Dabei ist ${\displaystyle \Phi _{i}^{B_{s}}(x)[s]}$ das Ergebnis der ersten ${\displaystyle s}$ Schritte der Berechnung von ${\displaystyle \Phi _{i}^{B_{s}}(x)}$.
3. ${\displaystyle x}$ wird zu ${\displaystyle A_{s+1}}$ hinzugefügt.
4. Sei z die größte Orakelanfrage, die bei der Berechnung von ${\displaystyle \Phi _{i}^{B_{s}}(x)}$ gestellt wurde. Dann wird die B-Beschränkung z hinzugefügt.
5. In jedem späteren Schritt ${\displaystyle 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 ${\displaystyle R_{2i+1}}$ haben analoge Strategien, in denen A und B vertauscht sind.

Dabei beginnt die Strategie für die ${\displaystyle n}$-te Anforderung ihre Aktivität im ${\displaystyle n}$-ten Schritt der Konstruktion bei (1). In jedem Schritt ${\displaystyle s}$ sind alle Strategien ${\displaystyle R_{k}}$ für ${\displaystyle 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 ${\displaystyle A_{s}}$ und ${\displaystyle B_{s}}$ berechenbar.

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

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

Analog lässt sich zeigen, dass alle ${\displaystyle 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. 

Einzelnachweise

1. J.C.E.Dekker: A theorem on hypersimple sets. In: Proceedings of the American Mathematical Society. Band 5, 1954, S. 791–796.