Orakel

Man ist im Allgemeinen nicht nur daran interessiert, ob und wie gut ein Problem berechenbar ist, sondern auch daran, wie sich Probleme relativ zueinander verhalten. Hierzu führt man Orakel ein. Ein Orakel ist eine zusätzliche Anweisung einer Maschine, die ein konkretes Problem lösen kann, ohne dafür Zeit zu brauchen.

In Registermaschinen kann man zum Beispiel einen Befehl oracle R[i] R[j] ... einführen. Bei Turingmaschinen würde man ein zusätzliches Band einführen, auf das man dann das Orakel anwenden kann. Wichtig ist jedenfalls, besonders später in der Komplexitätstheorie, dass dieses Orakel keine Zeit braucht.

Turing-Reduzierbarkeit

Von Turing-Reduzierbarkeit zwischen zwei Problemen $A$ und $B$, geschrieben $A \le_T B$, redet man, wenn es eine Orakel-Turingmaschine $M$ gibt, mit einem Orakel für $B$, die damit das Problem $A$ lösen kann.

Beispielsweise lässt sich das Post'sche Korrespondenzproblem $PCP$ wie vorher gezeigt zurückführen auf das Halteproblem $H$, also $H \le_T PCP$. Allgemein sind die meisten Unentscheidbarkeitsbeweise Turing-Reduktionen auf das Halteproblem und verwandte Probleme.

Jenseits von Unentscheidbarkeit

Die Betrachtung von Maschinen mit Halteproblem-Orakel macht nicht nur Sinn, um andere Probleme mit dem Halteproblem zu vergleichen. Man kann dieses Maschinenmodell auch einfach so betrachten. Turingmaschinen mit Halteproblem-Orakel haben insbesondere wieder ein eigenes, neues, schwereres Halteproblem. In diesem Halteproblem kann man wiederum eine neue Orakelturingmaschine definieren, und wenn man dies fortsetzt, erhält man eine Hierarchie von immer komplizierteren Halteproblemen. Wir werden TODO später sehen, dass man diese Orakelturingmaschinen verwenden kann, um die Schwierigkeit bestimmter arithmetischer Formeln zu klassifizieren.

Der Satz von Friedberg und Muchnik

Eine weitere Frage, die man sich stellen kann, ist, ob es auch unentscheidbare Probleme gibt, die nicht Turingreduzierbar auf das Halteproblem sind. Das heißt, ein Problem, das "echt leichter" ist als das Halteproblem, aber dennoch "echt schwerer" als alle berechenbaren Probleme.

Der von Friedberg und Muchnik beweist, dass es in der Tat solche Probleme gibt.