9.1 Das Zeithierarchietheorem

Das Zeithierarchietheorem besagt, dass es zu jeder "vernünftigen" Komplexitätsfunktion $t : N \to N$ ein Entscheidungsproblem $L \subseteq Σ^{*}$ gibt, dass man in Zeit $t$ entscheiden kann, aber nicht deutlich schneller. Was "vernünftig" bedeutet, wird weiter unten klar werden. Wir betrachten noch einmal genauer die universelle Turingmaschine aus Kapitel 7.5. Unsere Implementierung hatte insgesamt fünf Bänder verwendet: (1) ein Band, um die Regeln von $M$ zu speichern (also die Funktion $δ$ ); (2) ein Band, um den Zustand von $M$ zu speichern; (3) um den akzeptierenden Zustand $q_{y e s}$ von $M$ zu speichern; (4) und (5) um das Band von $M$ zu simulieren. Für letzteres hatten wir zwei Bänder verwendet, weil das uns erlaubte, effizient Zeichen einzufügen statt einfach zu überschreiben. Wie wir aber gesehen hatten, können wir (4) und (5) mit einem Band bewältigen, indem wir zu allererst die Codierung $enc (M)$ durchgehen und die Länge $l$ des längsten Bandzeichen bestimmen. Wir verwenden dann auf Band (4) immer Blöcke der Länge $l$ für ein $M$ -Zeichen und separieren diese durch eine Markierung $#$ . Auch das Band (3) können wir uns sparen: den akzeptierenden Zustand von $M$ können wir gleich am Anfang von (1) schreiben, ohne das die Simulation dadurch nennenswert teurer würde. Wir kommen also mit drei Bändern aus. Allerdings hatten wir uns nur überlegt, wie man Einband-Turingmaschinen $M$ simuliert. Es ist aber ziemlich einfach zu sehen, dass man Codierung und Simulation ganz analog für $k$ -Band-Turingmaschinen durchführen kann. Die entsprechende Turingmaschine hat dann allerdings $k + 2$ Bänder: $k$ Arbeitsbänder, eins für den Zustand von $M$ und eins für $enc (M)$ . Darüberhinaus hatten wir in Kapitel 7.7 gesehen, dass wir als Codierungsalphabet $Σ$ selbst nehmen können, also $enc (M) \in Σ^{*}$ , solange $Σ$ mindestens zwei Zeichen enthält.

Theorem 9.1.1 Für jedes Alphabet $Σ$ mit mindestens zwei Zeichen und jedes $k \geq 1$ gibt es eine Turingmaschine $U$ mit $k + 2$ Bändern, die folgendes kann: sei $M$ eine beliebige $k$ -Band-Turingmaschine mit Eingabealphabet $Σ$ und sei $x \in Σ^{*}$ . Dann gilt

\begin{array}{r} f_{U} (enc (M) x) = f_{M} (x) . \end{array}

Weiterhin gilt: wenn $M$ auf $x$ innerhalb von $s$ Schritten terminiert, dann terminiert $U$ auf $enc (M) x$ innerhalb von

\begin{array}{r} C \cdot | enc (M) | \cdot (| x | + s) \end{array}

Schritten. Das $C$ ist hier eine absolute Konstante, hängt also weder von $M$ noch von $Σ$ ab.

Dass es so ein $U$ gibt, hatten wir ja schon gesehen. Gehen wir aber noch einmal die Zeitschranke durch. In einer vorbereitenden Phase bestimmt $U$ die Länge $l$ des längsten Bandzeichen von $M$ . Dann schreibt es das Eingabewort $x_{1} x_{2} \dots x_{n}$ als Folge von Blöcken der Länge $l$ auf das Arbeitsband. Zellen in einem Block, die nicht verwendet werden, werden mit einem $-$ gefüllt. Hier ein Beispiel für den Fall $l = 4$ :

\begin{array}{r} # x_{1} - - - # x_{2} - - - # x_{3} - - - # \dots # x_{n} - - - # \end{array}

Diese Vorbereitungsphase benötigt maximal $C \cdot | enc (M) | \cdot | x |$ Schritte. Um nun einen Schritt von $M$ zu simulieren, müssen wir das gerade gelesene $M$ -Zeichen $z$ auf Band 2 schreiben, so dass dann dort $enc (q), enc (z)$ steht. Das braucht $l + 1$ Schritte. Als nächstes müssen wir $δ_{M} (q, z)$ bestimmen, müssen wir $enc (M)$ durchgehen und den Eintrag für $enc (q), enc (z)$ suchen, was maximal $2 \cdot enc (M)$ Schritte benötigt. Dann müssen wir den Schritt ausführen, also den neuen Zustand auf Band 2 schreiben, das neue Zeichen in den Block auf dem Arbeitsband eintragen und den Kopf bewegen. All das benötigt maximal $C \cdot | enc (M) |$ Schritte.

Untere Schranken für Zeitkomplexität

Wir wollen nun eine Sprache definieren, die wir in $t (n)$ Schritten entscheiden können aber nicht deutlich schneller. Wir erinnern uns an $H A L T$ , die von der universellen Turingmaschine $U$ akzeptierte Sprache:

\begin{array}{r} H A L T := L (U) = {enc (M) w | M akzeptiert w} . \end{array}

und davon abgeleitete "Diagonalisierungssprache"

\begin{array}{r} NegDiag := {enc (M) \in Σ^{*} | enc (M) enc (M) \notin H A L T} \end{array}

Wir haben gesehen, dass $NegDiag$ nicht entscheidbar ist. Nun wollen wir eine Version von $NegDiag$ , die in $t$ Schritten entscheidbar ist, aber nicht in sehr viel weniger. Dafür definieren wir uns ein Halteproblem mit Zeitbudget.

Definition 9.1.2 (Zeitbudgetiertes Halteproblem). Sei $Σ$ ein endliches Alphabet. Wir definieren die Sprache $\begin{array}{r} T I M E D H A L T := {enc (M) 1^{b} 0 x | U akzeptiert enc (M) x innerhalb von b Schritten} \end{array}$ Mit $1^{b}$ bezeichnen wir die Folge von $n$ vielen $1$ en. Des Weiteren ist $M$ eine $k$ -Band-Turingmaschine mit Eingabealphabet $Σ$ und $x \in Σ^{*}$ und $U$ die universelle Turingmaschine, die selbst $k + 2$ Bänder hat. Wir sollten strenggenommen also ${T I M E D H A L T}_{Σ, k}$ definieren, unterlassen dies aber der Lesbarkeit halber.

Bitte erinnern Sie sich daran, dass unsere Codierung $enc (M)$ immer mit dem Sonderzeichen $;$ endet, oder besser gesagt: mit der Codierung von $; \in Λ$ über dem Alphabet $Σ$ selbst. Eine Turingmaschine kann also, gegeben ein Eingabewort $enc (M) 1^{b} 0 x$ , dieses in die Bestandteile $enc (M)$ , $1^{b}$ , $0$ und $x$ zerlegen. Die $0$ dient dazu, das "Budget" $1^{b}$ vom "inneren Eingabewort" $x$ abzugrenzen.

Beobachtung 9.1.3 $T I M E D H A L T \in {TIME}_{k + 3} (n)$ .

Beweis. Wir nehmen die universelle Turingmaschine $U$ , die $k$ -Band-Turingmaschinen simulieren kann, und statten sie mit einem Stoppuhrband aus. Sie hat nun also $k + 3$ Bänder. Sei $n = | enc (M) | + b + 1 + | x |$ die Länge des Eingabewortes. In $O (n)$ Schritten sorgt sie dafür, dass auf dem Eingabeband das Wort $enc (M) x$ steht und auf dem Stoppuhrband das Budget $1^{b}$ . Nun lassen wir die universelle Turingmaschine $U$ laufen, nur dass wir in jedem Schritt den Kopf auf dem Stoppuhrband nach rechts verschieben. Wenn $U$ hält, dann hält unsere Turingmaschine auch und gibt das gleiche Ergebnis aus. Wenn wir das Ende des Stoppuhrbandes erreicht haben, haben wir unsere $b$ Schritte verbraucht und lehnen ab. Wir brauchen insgesamt $O (n + b) = O (n)$ Schritte.

◻

Sei nun $t : N \to N$ eine monoton steigende Funktion mit $t (n) \geq n$ . Wir definieren eine Zeitbudgetierte Version der Diagonalisierungssprache:

\begin{array}{r} TimedNegDiag := {enc (M) 1^{m} | enc (M) 1^{b} 0 enc (M) 1^{n} \notin T I M E D H A L T, b = t (| enc (M) | + m)} \end{array}

Behauptung 9.1.4 (nicht ganz korrekt). $TimedNegDiag \in {TIME}_{k + 3} (t)$ .

Sei $n := | enc (M) + m |$ die Länge des Inputwortes. Wir können $TimedNegDiag$ entscheiden, indem wir aus $enc (M) 1^{m}$ den String $enc (M) 1^{b} 0 enc (M) 1^{m}$ berechnen und dann die Turingmaschine für $T I M E D H A L T$ laufen lassen, welche $k + 3$ Bänder hat und selbst $O (2 | enc (M) | + b + 1 + m) = O (| enc (M) | + b) = O (b)$ Schritte braucht. Die Vorbereitungsphase braucht ungefähr so lange, wie wir brauchen, um $b = t (| enc (M) + m |) = t (n)$ zu berechnen. Übliche Zeitschranken $t$ , die uns interessieren, wären zum Beispiel $n \log n$ , $n^{2}$ , $2^{n}$ , $n!$ oder $n^{n}$ . All diese stellen kein Problem dar. Insgesamt sind wir auf der sicheren Seite, wenn wir die Funktion $t$ selbst in $O (t)$ Schritten berechnen können.

Definition 9.1.5 Eine Funktion $t : N \to N$ heißt zeitkonstruierbar, wenn es eine Turingmaschine gibt, die aus dem Eingabewort $1^{n}$ das Ausgabewort $1^{t (n)}$ berechnet und selbst maximal $O (t (n))$ Schritte läuft.

Behauptung 9.1.6 (jetzt korrekt). Sei $t : N \to N$ zeitkonstruierbar, monoton steigend und $t (n) \geq n$ . Dann gilt $TimedNegDiag \in {TIME}_{k + 3} (t)$ .

So weit, so gut. Wonach wir allerdings aus sind, ist ein Beweis, dass $TimedNegDiag$ nicht signifikant schneller zu berechnen ist.

Lemma 9.1.7 Sei $s : N \to N$ eine Funktion mit $s (n) \geq n$ und $s = o (t)$ , also $lim_{n \to \infty} \frac{s (n)}{t (n)} = 0$ . Dann gilt $TimedNegDiag \notin {TIME}_{k} (s)$ .

Beweis. Wir nehmen an, es gäbe eine Turingmaschine $M$ , die $TimedNegDiag$ in Zeit $s$ entscheidet und leiten einen Widerspruch her. Sei $x := enc (M)$ . Wir wählen eine natürliche Zahl $m$ , deren genauen Wert wir weiter unten diskutieren und setzen $b := t (| x | + m)$ . Wir fragen uns nun: ist $x 1^{m} \in TimedNegDiag$ ?

\begin{aligned} x 1^{m} \in TimedNegDiag & ⟺ enc (M) 1^{b} 0 x 1^{m} \notin T I M E D H A L T \\ ⟺ U lehnt enc (M) x 1^{m} innerhalb von b Schritten ab \end{aligned}

Langsam nun. Sei $n := | enc (M) | + m$ die Länge des Wortes $x 1^{m}$ . Nach Annahme terminiert $M$ auf dem Eingabewort $x 1^{m}$ innerhalb von $s (n)$ Schritten. Wenn $U$ die Maschine $M$ simuliert, braucht sie nach Theorem 8.1.1 höchstens $C \cdot | enc (M) | \cdot (n + s (n))$ Schritte. Da $s (n) \geq n$ gilt, sind dies höchstens $2 C \cdot | enc (M) | \cdot s (n) = 2 C \cdot | enc (M) | \cdot s (| x | + m)$ Schritte. Da $lim_{n \to \infty} \frac{s (n)}{t (n)} = 0$ ist, ist auch

\begin{array}{r} lim_{m \to \infty} \frac{2 C \cdot | enc (M) | \cdot s (| x | + m)}{t (| x | + m)} = 0 . \end{array}

Wenn wir also $m$ hinreichend groß wählen, dann ist dieser Bruch kleiner als $1$ , und die Simulation terminiert also innerhalb von

\begin{array}{r} 2 C \cdot | enc (M) | \cdot s (| x | + m) \leq t (| x | + m) = b \end{array}

Schritten. Das heißt, dass die universelle Turingmaschine $U$ das Wort $enc (M) x 1^{m}$ innerhalb von $b$ Schritten ablehnt, wenn sie es überhaupt irgendwann ablehnt. Also schließen wir weiter:

\begin{aligned} x 1^{m} \in TimedNegDiag & ⟺ enc (M) 1^{b} 0 x 1^{m} \notin T I M E D H A L T \\ ⟺ U lehnt enc (M) x 1^{m} innerhalb von b Schritten ab \\ ⟺ U lehnt enc (M) x 1^{m} ab \\ ⟺ M lehnt x 1^{m} ab \end{aligned}

und da ist er, der Widerspruch: $x 1^{m} \in TimedNegDiag ⟺ f_{M} (x 1^{m}) = reject$ , entgegen unserer Annahme, dass $M$ die Sprache $TimedNegDiag$ entscheidet. $◻$

Zusammenfassend erhalten wir die "Rohversion" des Zeithierarchiesatzes:

Theorem 9.1.8(Zeithierarchiesatz, Rohversion). Seien $s, t : N \to N$ zeitkonstruierbare Funktionen mit $s (n) \geq n$ und $s \in o (t)$ (also $lim_{n \to \infty} s (n) / t (n) = 0$ ). Dann gilt

\begin{array}{r} {TIME}_{k} (s) ⊊ {TIME}_{k + 3} (t) \end{array}

für alle $k \geq 1$ .

Zusammen mit der Simulation von $k$ -Band-TMs durch $2$ -Band-TMs folgt nun

\begin{array}{r} TIME (s) ⊊ {TIME}_{2} (s \log s) ⊊ {TIME}_{5} (t \log t) \end{array}

oder, alternativ ausgedrückt:

Theorem 9.1.9 (Zeithierarchiesatz). Seien $s, t : N \to N$ mit $s (n) \geq n$ und $s \log s \in o (t)$ . Dann gilt $TIME (s) ⊊ TIME (t)$ .

Bitte beachten Sie, dass wir diese Version nicht vollständig bewiesen habe, da ich die effizientere Simulation einer $k$ -Band-Turingmaschine durch eine $2$ -Band-Turingmaschine, also ${TIME}_{k} (t) \subseteq {TIME}_{2} (t \log t)$ nicht erklärt habe. Mit der ineffiziten, also ${TIME}_{k} (t) \subseteq {TIME}_{1} (t^{2})$ , erhalten wir einen Zeithierarchiesatz solange $s^{2} \in o (t)$ ist.

Übungsaufgabe 9.1.1 Zeigen Sie, dass $n \mapsto n^{2}$ und $n \mapsto 2^{n}$ zeitkonstruierbar sind.