Orakel-Turingmaschine

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

Eine Orakel-Turingmaschine ist eine Turingmaschine $M$ , die mit einem Orakel verbunden ist. Bildhaft kann man sich ein Orakel als eine black box vorstellen, die von $M$ befragt werden kann und ein Problem in einem Schritt löst. Dadurch sind Orakel-Turingmaschinen in der Lage, Probleme einer gegebenen Komplexitätsklasse in konstanter Zeit zu entscheiden.

[Bearbeiten] Definition

Sei $A\subseteq \Sigma^*$ eine Sprache über dem Alphabet $Σ$ . Eine Orakel-Turingmaschine mit Orakel $A$ ist eine Turingmaschine $M$ mit einem zusätzlichen Eingabeband (Orakelband) und drei ausgezeichneten Zuständen: $q j, q n, q ?$ . Schreibt $M$ ein Wort $w\in\Sigma^*$ auf das Orakelband und geht in den Zustand $q ?$ über, so befragt $M$ das Orakel: Der Nachfolgezustand von $q ?$ sei $q j$ falls $w\in A$ gilt und andernfalls $q n$ . Anschließend wird das Orakelband gelöscht.

Die Sprache $A$ kann natürlich eine höhere Komplexität haben als die Sprache, die $M$ selbst berechnen kann, ohne das Orakel zu befragen.

Die Sprache, die $M$ akzeptiert, ist $L (M A): = {w | M akzeptiert w mit Orakel A}$ .

Sei $K$ eine Komplexitätsklasse (wie NP) und $A$ eine Sprache. Dann seien:

$P A : = {L (M A) | M$ ist eine deterministische, polynomiell zeitbeschränkte Orakel-Turingmaschine mit Orakel $A}$
$N P A : = {L (M A) | M$ ist eine nichtdeterministische, polynomiell zeitbeschränkte Orakel-Turingmaschine mit Orakel $A}$
$P^K:=\bigcup_{A\in K}P^A$
$NP^K:=\bigcup_{A\in K}NP^A$

Diese Komplexitätsklassen werden unter anderem dazu genutzt, um die Polynomialzeithierarchie zu definieren. Ähnlich lassen sich für andere Komplexitätsklassen $C$ die Begriffe $C A$ und $C K$ definieren.

[Bearbeiten] Eigenschaften

Es gilt offensichtlich $P P = P$ , denn anstatt für Problem aus $A\in P$ ein Orakel zu befragen, kann eine deterministische polynomiell beschränkte Turingmaschine das Problem selbst berechnen.

Weiterhin gilt $NP\subseteq P^{NP}$ (Beweis: Sei $L\in NP$ . Dann entscheidet die determinstische Turingmaschine, die bei Eingabe $w$ das Wort $w$ auf das Orakelband schreibt, in den Zustand $q ?$ übergeht und genau dann akzeptiert, wenn der Nachfolgezustand $q j$ ist, in Linearzeit die Sprache $L$ ).

[Bearbeiten] Halteproblem

Die Definition der Orakel-Turingmaschine setzt nicht voraus, dass das Orakel $A$ entscheidbar oder gar semi-entscheidbar ist. Also gibt es Orakel-Turingmaschinen, die das Halteproblem von Turingmaschinen (ohne Orakel) lösen können. Allerdings lassen sich für diese Maschinen wiederum nicht entscheidbare Halteprobleme konstruieren.