eine Turing-Maschine, die mit einem zusätzlichen Band, dem Orakelband, ausgestattet ist.

Zu jedem Zeitpunkt im Laufe ihrer Rechnung kann die Orakel-Turing-Maschine in einen speziellen Zustand, den Orakel-Befragungszustand übergehen. Der direkt darauf folgende Zustandsübergang hängt nicht von der Zustandsübergangsfunktion der Turing-Maschine ab, sondern von einer vorgegebenen MengeA, dem „Orakel“. Je nachdem, ob die Inschrift des Orakelbandes zu diesem Zeitpunkt ein Element von A ist oder nicht, geht die Maschine in einen speziellen Zustand q₊ oder q₋ über. Die von einer Orakel-Turing-Maschine akzeptierte Sprache oder berechnete Funktion hängt damit von dem vorgegebenen Orakel A ab.

Mit Hilfe von Orakel-Turing-Maschinen läßt sich das Konzept der relativen Berechenbarkeit einführen: Die von der Orakel-Turing-Maschine berechnete Funktion f ist berechenbar relativ zur Orakelmenge A. Formal schreibt man f ≤_T A (sprich: f ist Turing-reduzierbar nach A). Für eine Menge B schreibt man B ≤_T A, sofern die charakteristische Funktion von B auf A Turing-reduzierbar ist.

Es gilt: Wenn B ≤_T A und A entscheidbar oder rekursiv aufzählbar ist, so ist auch B entscheidbar bzw. rekursiv aufzählbar (Entscheidbarkeit).