Satz von Cook über TM mit Stack
cook_stack.txt
—
Plain Text,
3 KB (4062 bytes)
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.
Artikelaktionen