Vorbemerkungen

Sei ${\displaystyle L:=L(G)}$ eine Sprache über der Typ-1-Grammatik ${\displaystyle G:=(N,\Sigma ,\delta ,S)}$ mit den üblichen Symbolen für Nichtterminale ${\displaystyle N}$, Terminale ${\displaystyle \Sigma }$, Produktionsregeln ${\displaystyle \delta }$ und dem Startsymbol ${\displaystyle S}$. Dann ist für ein Wort ${\displaystyle w\in \Sigma ^{\ast }}$ der Graph ${\displaystyle Graph_{|w|}:=((\Sigma \cup N)^{\leq |w|},\alpha \Rightarrow _{G}\beta )}$ derjenige Graph, der alle Satzformen mit einer Länge höchstens der Länge von ${\displaystyle w}$ enthält, wobei der Graph genau dann eine Kante zwischen zwei Satzformen hat, wenn es eine Produktion in ${\displaystyle G}$ gibt. Insbesondere enthält der Graph sowohl ${\displaystyle S}$ als auch ${\displaystyle w}$ selbst und es gilt, dass ${\displaystyle w\in L}$ genau dann, wenn es einen Pfad von ${\displaystyle S}$ nach ${\displaystyle w}$ in diesem Graphen gibt.

Wenn es nun möglich ist, eine nichtdeterministische, linear beschränkte Turingmaschine zu konstruieren, die genau dann akzeptiert, wenn es keinen Pfad von ${\displaystyle S}$ nach ${\displaystyle w}$ gibt, ist der Beweis erbracht.

Nicht-Erreichbarkeit

Zunächst sei angenommen, dass die Anzahl ${\displaystyle N}$ der erreichbaren Knoten von ${\displaystyle S}$ bekannt ist (wir verschieben die Berechnung von ${\displaystyle N}$ auf später). Dann löst folgender Algorithmus die Nicht-Erreichbarkeit.

Gegeben Graph ${\displaystyle G=(V,E)}$, Startknoten ${\displaystyle s}$, Zielknoten ${\displaystyle t}$ und Anzahl erreichbarer Knoten ${\displaystyle N}$.

1. Initialisiere Zähler ${\displaystyle c:=0}$
2. Für jeden Knoten ${\displaystyle v\in V}$:
   • Rate nichtdeterministisch, ob ${\displaystyle v}$ von ${\displaystyle s}$ erreichbar ist und falls die Antwort positiv ist:
     • Rate nichtdeterministisch einen Pfad von ${\displaystyle s}$ nach ${\displaystyle v}$ der Länge höchstens ${\displaystyle |V|}$ und
     • falls der Pfad falsch war oder nicht zu ${\displaystyle v}$ führt, breche mit nein ab,
     • falls ${\displaystyle v=t}$, breche mit nein ab (denn der Knoten ist offenbar erreichbar),
     • ansonsten erhöhe den Zähler ${\displaystyle c}$ um eins.
3. Falls ${\displaystyle c<N}$, breche mit nein ab, ansonsten gebe ja aus.

Weder ${\displaystyle N}$ noch ${\displaystyle c}$ können größer als ${\displaystyle |V|}$ sein und verbrauchen demnach (binär kodiert) nicht mehr als ${\displaystyle \log(|V|)}$ Speicherplatz. Der Algorithmus stellt sicher, dass alle ${\displaystyle N}$ Knoten, die von ${\displaystyle s}$ erreichbar sind, aufgezählt werden und akzeptiert nur dann, wenn ${\displaystyle t}$ keiner dieser Knoten war.

Induktives Zählen

Es bleibt jetzt nur noch die bislang unbekannte Anzahl ${\displaystyle N}$ der erreichbaren Knoten zu ermitteln. Die Idee ist, die Anzahl ${\displaystyle N_{i}}$ der Knoten zu berechnen, die in höchstens ${\displaystyle i}$ Schritten erreichbar sind. Man lässt ${\displaystyle i}$ dann induktiv hochzählen und verwendet, dass ${\displaystyle N=N_{|V|}}$ gilt. Der Algorithmus funktioniert wie folgt:

1. Initialisiere ${\displaystyle N_{0}:=1}$ (der Startknoten benötigt keinen Schritt um erreicht zu werden)
2. Für jede Anzahl an Schritten ${\displaystyle i=1,\dots ,|V|}$:
   1. Initialisiere ${\displaystyle N_{i}:=0}$.
   2. ${\displaystyle \star }$ Für jeden Knoten ${\displaystyle v\in V}$:
      1. Initialisiere einen Zähler ${\displaystyle c:=0}$
      2. Für jeden Knoten ${\displaystyle u\in V}$:
         • Rate nichtdeterministisch, ob ${\displaystyle u}$ von ${\displaystyle s}$ in weniger als ${\displaystyle i}$ Schritten erreichbar ist.
         • Falls ja, rate einen Pfad von ${\displaystyle s}$ mit einer Länge kleiner ${\displaystyle i}$ und breche ab, falls der Pfad nicht in ${\displaystyle u}$ endet.
         • Falls so ein Pfad gefunden wurde, erhöhe den Zähler ${\displaystyle c}$ um eins und ...
         • ... wenn ${\displaystyle u}$ gleich ${\displaystyle v}$ ist oder es eine Kante von ${\displaystyle u}$ nach ${\displaystyle v}$ gibt, erhöhe ${\displaystyle N_{i}}$ ebenfalls um eins und setze die Iteration von ${\displaystyle v}$ fort (markiert mit ${\displaystyle \star }$).
      3. Falls ${\displaystyle c<N_{i-1}}$, breche die Berechnung ab
3. Gebe ${\displaystyle N_{|V|}}$ zurück.

Da sich der Algorithmus lediglich drei Zähler (${\displaystyle c,N_{i},N_{i-1}}$) gleichzeitig merken muss, lässt er sich mit logarithmischem Speicherplatz realisieren. Ein formaler Beweis der Korrektheit wird dem interessierten Leser überlassen. Als Beweisidee dient folgender Hinweis: ${\displaystyle N_{i}}$ wird genau dann nicht inkrementiert, wenn alle Knoten mit einer Distanz kleiner als ${\displaystyle i}$ ausprobiert wurden und kein weiterer direkt (d. h. in höchstens einem Schritt) erreichbarer Knoten gefunden werde konnte.

Der Beweis

Nun müssen lediglich beide Algorithmen kombiniert werden.

1. Berechne ${\displaystyle N}$ für ${\displaystyle G:=Graph_{|w|}}$ und ${\displaystyle s:=S}$ durch induktives Zählen.
2. Benutze Nicht-Erreichbarkeit für ${\displaystyle G:=Graph_{|w|},s:=S}$ und ${\displaystyle t:=w}$ mit zuvor berechnetem ${\displaystyle N}$.

Eine solche Turingmaschine akzeptiert genau dann, wenn es keinen Pfad von ${\displaystyle S}$ nach ${\displaystyle w}$ gibt und da beide Teilalgorithmen nur logarithmischen Speicherplatz benötigen, ist der Beweis komplett.