Satz von Friedberg und Muchnik

aus Wikipedia, der freien Enzyklopädie

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 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.

Strategien

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. 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.