Satz von Cook über TM mit Stack

Dateiinhalt

SATZ VON COOK: 

Definition (E/A-TM mit Stack): Eine Turing - Maschine mit Stack hat
mindestens 3 Baender: E, A und S. E ist das Nur-Lese Eingabeband, A
das Nur-Schreibe Ausgabeband und S ist ein Stack auf dem zwar gelesen
und geschrieben werden kann, aber immer nur in Stack-Disziplin,
d.h. der Kopf steht immer ganz rechts. Formal besteht hat solch eine
Maschine besondere Quintupel der Form 

(q,s,s',m,q',sa) 

hat, wobei q:Q, s:Sigma^k, s':Sigma^{k-1}, m:{L,R,S}^{k-1},
und sa eine Stack-Aktion ist: 

Entweder

1) sa = IDLE: das Stack-Band und der Stack-Kopf veraendern sich
   nicht. 
2) sa = POP: der Stack-Kopf rueckt eine Position nach links. Ist der
   Kopf schon auf der linkesten Bandposition, so bleibt die Maschine
   stehen. 
3) sa = PUSH(y), y:Sigma. Der Stack-Kopf rueckt eine Position nach
   rechts und schreibt y auf die neue Position. 

Zu Beginn befindet sich auf dem Stack-Band ein bestimmtes Symbol
A. Wird dieses also geloescht, so bleibt die Maschine stehen.  

Eine (nichtdeterministische) TM mit Stack ist f(n)-platzbeschraenkt, wenn nach Ende der
Berechnung auf Input x (auf E geschrieben) die Summe der Laengen aller
Arbeitsbaender ausser S <= f(|x|) ist. Der Stack S kann beliebig lang
sein. 

Die Komplexitaetsklasse (N)SPACE(f(n))+STACK bezeichnet alle Probleme, die
sich mit solch einer (nichtdeterministischen) TM loesen lassen.

Beispiel: Der Beweis des Satzes von Savitch zeigt, dass REACH: : LOGSPACE+STACKw

Satz (Cook): Sei f(n)>=log(n). Es ist SPACE(f(n))+STACK =
NSPACE(f(n))+STACK = TIME(2^c.f(n))

Beweis: Sei M eine SPACE(f(n))+STACK Maschine. Eine globale
Konfiguration von M ist definitionsgemaess eine globale Konfiguration
ohne Beruecksichtung des Stacks S, besteht also aus den Inhalten und
Kopfpositionen aller Arbeitsbaender, sowie der Kopfposition des
Eingabebandes. Man beachte, dass (wegen f(n)>=log(n)) eine solche
globale Konfiguration Platz O(f(n)) verbraucht, deren Zahl also
2^O(f(n)) ist. Sei nun x eine Eingabe, g eine globale
Konfiguration, U ein Symbol. Wir bezeichnen mit 

k(g,U) 

diejenige globale Konfiguration, die erreicht wird, wenn U ge-poppt
wird. Da dies moeglicherweise nie der Fall sein wird, ist k eine
partielle Funktion. Beachte: k haengt implizit auch von der Eingabe
ab. 

Man beachte, dass x in L(M) genau dann, wenn 

k(init,A) eine akzeptierende Konfiguration ist. 

OBdA (Aufraeumen etc) koennen wir von einer einzigen akzeptierenden
Konfiguration Accept ausgehen: 

x : L(M) <==> k(init,A) = Accept.

Nun erfuellt k folgende Rekurrenz: 

k(g,U) = t(g,U), falls das Symbol U im naechsten Schritt gepoppt
wird. t sei dann die entsprechende Folgekonfiguration, die sich aus
dem entsprechenden Quintupel ergibt. 

k(g,U) = k(t(g,U),U), falls das Symbol U stehenbleibt. 

k(g,U) = k(k(t(g,U),V),U), falls das Symbol V gepusht wird. 

Es liegt also eine geschachtelte Rekursion vor, bei deren Abarbeiten
sei es durch Termersetzung, sei es mit Frames wie in Java,  sich
natuerlich wiederum der Stack S reproduziert. 

Der Punkt ist nun, dass wir diese rekursive Funktion anstatt durch
echte Rekursion auch durch dynamische Programmierung, d.h. also durch 
Tabulierung aller 2^O(f(n)) Werte in Zeit 2^O(f(n)) berechnen
koennen. 


War die Maschine urspruenglich nichtdeterministisch, so brauchen wir
eine Relation 

k(g,U,g') <==> ausgehend von g mit oberstem Stacksymbol U kann nach
mehreren Schritten U gepoppt werden und damit Konfiguration g'
eingenommen werden. 

Es gilt

in g kann U sofort gepoppt werden und g' erreicht werden ==> k(g,U,g')
in g kann U stehenbleiben und g' erreicht werden, ausserdem gilt
k(g',U,g'') ==> k(g,U,g'')
in g kann V gepusht werden und g' eingenommen werden. 
Auf der anderen Seite geben wir uns eine 2^O(f(n))-zeitbeschraenkte
Maschine vor. Wir definieren die Funktion

k(x,t,a) = "das Symbol, das an der Stelle a zur Zeit t auf den
Baendern steht". Es gilt: 

k(x,0,a) = init
k(x,t+1,a) = ... k(x,t,.) ... k(x,t,.) ... 

Diese rekursive Funktion kann nun aber mithilfe eines Stacks (dessen
Hoehe exponentiell sein wird) ausgerechnet werden.