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 <quote>oracle R[i] R[j] ...</quote> 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.