Satz von Friedberg und Muchnik

Der Satz v​on Friedberg u​nd Muchnik i​st ein Ergebnis d​er Berechenbarkeitstheorie u​nd mathematischen Logik, d​as 1956/1957 unabhängig voneinander v​on Richard M. Friedberg u​nd Albert Muchnik bewiesen wurde. Es besagt, d​ass es rekursiv aufzählbare Turinggrade gibt, d​ie zwischen 0 u​nd 0 liegen. Damit g​ibt es a​lso rekursiv aufzählbare Mengen, d​ie nicht entscheidbar sind, a​ber im Sinne d​er Turingreduktion leichter a​ls das Halteproblem. Für i​hre Beweise entwickelten Friedberg u​nd Muchnik e​ine neue Beweistechnik, d​ie als Prioritätsmethode o​der Prioritätsargument bekannt i​st und d​ie zu e​iner wichtigen Technik i​n der Berechenbarkeitstheorie wurde.

Geschichte

Emil Post untersuchte i​n einer Arbeit v​on 1944 d​ie Turinggrade u​nd fragte, o​b es rekursiv aufzählbare Turinggrade zwischen 0 u​nd 0 gibt. Diese Frage w​urde als Postsches Problem bekannt. Post definierte d​ie einfachen Mengen u​nd konnte zeigen, d​ass diese u​nter der many-one-Reduktion strikt zwischen d​en entscheidbaren Mengen u​nd dem Halteproblem liegen, o​hne dies a​uch für d​ie stärkere Turingreduktion zeigen z​u können. J.C.E. Dekker zeigte 1954, d​ass dies unmöglich ist, d​a es einfache Mengen i​n 0 gibt.[1] Das Problem w​urde 1956/57 unabhängig voneinander v​on Friedberg u​nd Muchnik d​urch die n​eu entwickelte Prioritätsmethode gelöst. 1986 veröffentlichte Antonín Kučera e​ine neue Lösung, d​ie kein Prioritätsargument benötigt.

Beweis

Idee

Der folgende Beweis f​olgt der Darstellung v​on Cooper 2004 u​nd beruht a​uf den ursprünglichen Beweisen v​on Friedberg u​nd Muchnik.

Es werden simultan zwei rekursiv aufzählbare Mengen und konstruiert, die aufeinander jeweils nicht Turing-reduzierbar sind: und . Wenn diese Bedingungen erfüllt sind, folgt direkt die Aussage des Satzes. Denn wenn oder 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 eine berechenbare Aufzählung der Orakel-Turingmaschinen. Dann gibt es für jede Maschine zwei Anforderungen:

  • : beschreibt keine Turingreduktion von auf . Formal:
  • : beschreibt keine Turingreduktion von auf . Formal:

Wenn alle erfüllt sind, gibt es keine Turingreduktion von auf und es gilt . Analog gilt , wenn alle erfüllt sind.

Die Anforderungen sind nach ihrer Priorität geordnet, sodass höchste Priorität hat, zweithöchste etc.

Es werden berechenbare Folgen endlicher Mengen und konstruiert. A und B sind dann die unendlichen Vereinigungen dieser Folgen: und . Da die Folgen berechenbar sind, sind ihre Vereinigungen und rekursiv aufzählbar.

Es ist . Im -ten Schritt der Konstruktion werden aus und die Mengen und konstruiert. Die Konstruktion wird von Strategien übernommen. Jede der Anforderungen hat eine Strategie, die versucht, diese Anforderung zu erfüllen.

Intuition

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

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

Die Strategien arbeiten vollkommen analog, mit vertauschten Rollen von und . Diese Strategien können also analog -Beschränkungen einführen, welche die -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 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 höchste Priorität hat, wird es nie verletzt. Da es für jedes nur endlich viele Anforderungen mit höherer Priorität gibt, die alle nach Induktionsvoraussetzung nur endlich oft verletzt werden, wird ebenfalls nur endlich oft verletzt, da es nur von Strategien mit höherer Priorität verletzt werden kann.

Formalisierung

Jede Anforderung der Form hat eine Strategie, die sich wie folgt prozedural darstellen lässt:

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

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

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

  • wartet unendlich lang bei (2), d. h. wird für kein erfüllt. Dann ist entweder undefiniert oder gleich 1. Da nicht in liegt, ist in beiden Fällen erfüllt.
  • erreicht (5), ohne wieder verletzt zu werden. Da in (3) zu hinzugefügt wurde, ist . Andererseits ist . Aufgrund der von hinzugefügten B-Beschränkung hat sich der relevante Teil von nicht verändert und .

Analog lässt sich zeigen, dass alle 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. 236238 (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. 493500.
  • 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.