Raumhierarchiesatz

Einfache Sprache

Def. Raumhierarchiesatz

Für jede Raumkonstruierbare Funktion $f:\mathbb N\to\mathbb N$ existiert eine Sprache $A$ so, dass $A$ entscheidbar ist in dem Raum $O(f(n))$ aber nicht in dem Raum $o(f(n))$.

Beweisidee: Zu zeigen ist

1. eine Sprache $A$ die entscheidbar in Raum $O(f(n))$ ist aber
2. nicht entscheidbar in Raum $o(f(n))$ ist.

Dazu benutzen wir Algorithmus $D$ der $A$ entscheidet. Da $D$ in Raum $O(f(n))$ läuft ist Erstens gegeben. Trick is es jetzt $D$ so zu definieren, das $A$ anders als alle anderen Sprachen in $o(f(n))$ ist. Dadurch ist Zweitens gegeben.

Beachte, dass hier ist $A$ besonders in dem Sinne, dass A erst (nur) durch $D$ definiert wird, also keine “nichtalgorithmische” Darstellung hat.

Aber wie kann man Sicher sein das $A$ nicht entscheidbar ist in $o(f(n))$? Dazu wird $D$ Diagonalisierung benutzen. Sei $\mathcal M$ eine TM die eine Sprache in dem Raum $o(f(n))$ entscheidet. Dann wird $D$ garantieren das $A$ mindestens an einer Stelle unterschiedlich von $\mathcal M$s Sprache ist. Die Stelle wird die Kodierung von $\mathcal M$ selbst sein.

Die funktioniert $D$ grob? $D$ hat als Eingabe die Kodierung einer TM $\mathcal M$. (Falls die Eingabe keine korrekte Kodierung einer TM ist, dann verwirft $D$ einfach.) Dann simuliert $D$ $\mathcal M$ auf der Eingabe $\langle \mathcal M\rangle$, also auf sich selbst, aber nur im Raum $f(n)$. Genau dann wenn $\mathcal M$ im Raum $f(n)$ verwirft, akzeptiert $D$. Falls $\mathcal M$ mehr Raum braucht dann verwirft $D$. Also wenn $\mathcal M$ im dem Raum $f(n)$ läuft, hat $D$ genug Platz um sicherzustellen das die Sprache von $D$ anders ist als die von $\mathcal M$.
Falls nicht $D$ nicht genug Platz hat um herauszufinden, was $\mathcal M$ tut, ist das nicht schlimm, weil die Anforderung an $D$ ja nur ist, dass sie unterschiedlich zu TMs die im Raum $o(f(n))$ laufen. Damit ist in diesem Fall die Ausgabe von $D$ irrelevant.

Beweis: Der folgende Algorithmus $D$ mit einer Platzkomplexität $O(f(n))$ entscheidet eine Sprache $A$, die nicht im Raum $o(f(n))$ entscheidbar ist. Für die Eingabe $w$ funktioniert $D$ wie folgt:

1. Sei $n$ die Länge von $w$.
2. Berechne $f(n)$, da $f$ raumkonstruierbar, und markiere $f(n)$ viel Speicher auf dem Band. Falls folgende Schritte mehr Speicher verwenden verwerfe.
3. Falls $w$ nicht von der Form $\langle \mathcal M\rangle 10^*$ ist, wobei $\langle\mathcal M\rangle$ eine Kodierung einer TM ist, verwerfe.
4. Simuliere $\mathcal M$ auf $w$. Inkrementiere dabei für jeden Schritt den $\mathcal M$ macht einen Zähler. Falls der Zähler größer $2^{f(n)}$ ist, verwerfe.
5. Falls $\mathcal M$ akzeptiert, verwerfe. Sonst akzeptiere.

Bleibt zu zeigen wie viel Raum dieser Algorithmus verwendet. Das wird in Schritt 4 entschieden. Da $\mathcal M$ ein beliebiges Bandalphabet hat und $D$ ein festes Bandalphabet hat, muss $D$ die Symbole von $\mathcal M$ durch mehrere Symbole repräsentieren. Daher hat $D$ einen konstanten Overhead bzgl. des benötigten Platzes. Wenn also $\mathcal M$ im Raum $g(n)$ läuft, dann braucht $D$ $dg(n)$ Raum, wobei $d$ eine Konstante die von $\mathcal M$ abhängt.

Sei $A$ die Sprache die $D$ entscheidet. Dann ist $A$ in $O(f(n))$ entscheidbar, weil $D$ in $O(f(n))$ läuft. Jetzt is noch zu Zeigen, dass $A$ nicht entscheidbar in $o(f(n))$ ist.

Nehme an das eine TM $\mathcal M$ $A$ entscheidet im Raum $g(n)\in o(f(n))$. Wir wissen das $D$ $\mathcal M$ im Raum $dg(n)$ simulieren kann. Weil $g(n)$ in small o von $f(n)$, existiert eine Konstante $n_0$ so, dass $dg(n)< f(n)$ für alle $n\geq n_0$. Daher wird $D$ die Simulation von $\mathcal M$ beenden wenn die Eingabe länger oder gleich $n_0$ ist. Wenn also $D$ auf der Eingabe $\langle\mathcal M\rangle 10^{n_0}$ läuft, ist die Eingabe länger als $n_0$ und $D$ würde die Simulation beenden. Daher würde, gegeben einer Eingabe, $D$ das Umgekehrte von $\mathcal M$ entscheiden. Also entscheidet $\mathcal M$ $A$ nicht, was unserer Annahme widerspricht. Es folgt das $A$ nicht im Raum $o(f(n))$ entscheidbar ist.