Direkt zum Inhalt

Lexikon der Mathematik: Orakel-Turing-Maschine

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 fT A (sprich: f ist Turing-reduzierbar nach A). Für eine Menge B schreibt man BT A, sofern die charakteristische Funktion von B auf A Turing-reduzierbar ist.

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

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos