Orakel-Turingmaschine

Einfache Sprache

Eine Orakel-Turingmaschine ist ein TM die mit einem Orakel verbunden ist. Je nachdem was für Information das Orakel liefert kann die TM dadurch mehr Sprachen entscheidet. So kann z.B. eine TM mit einem Orakel was SAT löst,

Def. Orakel-Turingmaschine

Gegeben ein Orakel für die Sprache $A$. Eine Orakel TM $\mathcal M^A$ ist eine modifizierte TM, die als zusätzliche Funktion das Orakel für $A$ abfragen kann. Genauer gesagt kann $\mathcal M^A$ einen Zeichenkette auf das so genannte Orakelband schreiben und erfährt in einem Berechnungsschritt ob die Zeichenkette teil der Sprache $A$ ist.