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. SATZ VON COBHAM Ziel ist eine Charakterisierung der PTIME Funktionen mittels einer Einschraenkung der primitiven Rekursion. Notationsrekursion: f = rec(g,h) bedeutet: f(0,xs) = g(xs) f(x,xs) = h(x,f(x/2,xs),xs) falls x>0 Fallunterscheidung: f = cond(g,h0,h1) f(0,xs) = g(xs) f(2x,xs) = h0(x,xs) f(2x+2,xs) = h1(x,xs) Man schreibt: f(x,xs) = match x with 0 -> g(xs) | S0(x) -> h0(x,xs) | S1(x) -> h1(x,xs) "Nachfolger": S0(x) = 2x S1(x) = 2x+1 Faktum: Mit Notationsrekursion, Fallunterscheidung, S0, S1, Konstanten und Variablen ( = Projektionen) lassen sich alle primitiv rekursiven Funktionen definieren. concat(0,y) = y concat(S0(x),y) = S0(concat(x,y)) concat(S1(x),y) = S1(concat(x,y)) Abkuerzung fuer entsprechende Definition mit Rec und match. code(0) = 0 code(x) = concat(code(x/2),code(x/2)) succ(0) = S1(0) succ(S0(x)) = S1(x) succ(S1(x)) = S0(succ(x/2)) decode(0) = 0 decode(x) = succ(x/2) Fuer decode(x) schreibt man auch |x|. decode(x) ist gerade die Laenge der Binaerdarstellung von x. Es gilt |x|=decode(x)=[log_2(x+1)]. Man zeigt: ist f(x1..xn) primitiv rekursiv, so ist g(y1..yn) mit g(code(x1),..,code(xn)) = code(f(x1,..,xn)) definierbar durch Notationsrekursion, Fallunterscheidung, ... Abhilfe: Definition: Beschraenkte Notationsrekursion: f wird aus g,h,k durch beschraenkte Notationsrekursion definiert (f = BRec(g,h,k)), wenn gilt: f(0,xs) = g(xs) f(x,xs) = h(x,f(x/2,xs),xs) falls x>0 und ausserdem f(x,xs) <= k(x,xs) Definition (Smash): x # y = 2^(|x|.|y|). Es gilt |x # y| = |x|.|y|, insbesondere |x#...#x| = |x|^n. Satz von Cobham: Die Klasse der in polynomialer Zeit berechenbaren Funktionen auf natuerlichen Zahle n(in Binaerdarstellung) stimmt mit der Klasse der Funktionen ueberein, die mit beschraenkter Notationsrekursion, Fallunterscheidung, S0,S1,# definierbar sind. Beispiele: concat(x,y) ist auch durch beschraenkte Notationsrek definierbar, da k(x,y)=x#y eine Schranke bildet. code(x) ist nicht durch beschraenkte Notationsrek definierbar, da man leicht zeigt, dass zu jeder so definierbaren Funktion ein Polynom p existiert, derart dass |f(xs)| <= p(|xs|). Beweis des Satzes: Fuer die eine Richtung beweist man durch Induktion ueber die Darstellung: Fuer alle Funktionen f(xs) aus Cobhams Klasse existiert ein Polynom p sodass gilt: f(xs) ist in Zeit p(|xs|) berechenbar (und es gilt insbesondere |f(xs)| <= p(|xs|)). Fuer die umgekehrte Richtung muss man zu gegebener deterministischer Turingmaschine eine Funktion definieren (in Cobhams System), die einen Schritt auf einer globalen Konfiguration durchfuehrt. Polynomial lange Iteration dieser Ein-Schritt Funktion liefert dann die jede beliebige PTIME Funktion. SICHERE REKURSION: Man teilt die Argumente einer Funktion in sichere und normale ein. Die sicheren Argumente duerfen nur "sicher" verwendet werden (was das heisst wird gleich gesagt). In der Notationsrekursion bestimmte Argumente sicher sein. Genauer gesagt muessen rekursive Aufrufe ueber sichere Argumente erfolgen. Auf der anderen Seite sind Argumente, ueber die rekurriert wird, immer als "normal" zu behandeln. Formal trennt man die normalen von den sicheren Argumenten durch ein Semikolon: f(xs;ys) bedeutet: die xs sind normal, die ys sind sicher. Die Funktionen des Systems BC sind nun wie folgt definiert. 1) Die Projektionen f(xs;ys)=yi und f(xs;ys)=xi sind in BC. 2) Die Konstante 0 und die Nachfolger S0(;x) und S1(;x) sind in BC (mit sicherem Argument). 3) Sind f(xs;ys) und g1(us;) bis gn(us;) und h1(us;vs) bis hm(us;vs) in BC, so auch f(g1(us;),...,gn(us;);h1(us;vs),...,hm(us;vs)). Sichere Komposition. Intuition: Kein sicheres Argument darf normal benutzt werden; will man einen Ausdruck in eine normale Position einsetzen, so darf der nicht von sicheren Argumenten abhaengen. Komposition mit einer Projektion erlaubt es, ein Argument von "sicher" auf "normal" herabzustufen. Heraufstufen geht aber nicht. 4) Sind g(xs;ys) h0(xs;y,ys) h1(y,ys) in BC so auch f=cond(g,h0,h1) gegeben durch f(xs;0,ys) = g(ys) f(xs;2y,ys) = h0(xs;y,ys) f(xs;2y+2,ys) = h1(xs;y,ys) Fallunterscheidung ueber ein sicheres Argument ist erlaubt. 5) Sind g(xs;ys) sowie h(x,xs;y,ys) in BC so auch f=rec(g,h) gegeben durch f(0,xs;ys) = g(xs;ys) f(x,xs;ys) = h(x,xs;f(x/2,xs;ys),ys) Rekursion nur ueber normale Argumente, Verwendung des rekursiven Aufrufs nur ueber sichere Position. Beispiele: concat(0;y) = y concat(S0(x);y) = S0(;concat(x;y)) concat(S1(x);y) = S1(;concat(x;y)) Formal concat = rec(g,h) wobei g(;y)=y h(x;z,y)=u(;x,z) und u=cond(g',h0,h1) wobei g'(z)=z, h0(;x,z)=S0(z), h1(;x,z)=S1(z). smash(0,x2;)=x2 smash(x1,x2;)=concat(x2;smash(x1/2,x2;)) |concat(x;y)| = |x| + |y| |smash(x1,x2)| = |x1|.|x2| Satz: ist f(xs) in FP, so existiert ein Polynom p, sowie eine BC definierbare Funktion h(z;xs) sodass gilt: |z| > p(|xs|) ==> h(z,xs) = f(xs) Korollar: ist f(xs) in FP, so kann f mit normalen Argumenten in BC repraesentiert werden. Satz: ist f(xs;ys) in BC repraesentierbar, so ist f in FP und es existiert ein Polynom p derart dass gilt |f(xs;ys)| <= p(|xs|)+max(|ys|). Korollar: BC=FP. ********************************************************************** LFPL. Idee: Bellantoni-Cook: Falls Sei g(0,y) = y g(t,y) = f(g(t/2,y)) und |f(x)| <= |x| + c, dann |g(t)| <= c.|t| + |y| Wenn jetzt aber h(0,y) = y h(t,y) = g(h(t/2),0) dann |h(t)| <= c^|t| Daher muss die Funktion g als "nicht iterierbar" markiert werden. Diese geschieht dadurch, dass das Argument t "nicht sicher" ist. Diese drastische Massnahme verbietet aber alle geschachtelten Iterationen und schliesst dadurch viele vernuenftige Algorithmen aus. LFPL liegt nun die Beobachtung zugrunde, dass eine Funktion, welche die Laenge ueberhaupt nicht erhoeht, iteriert werden kann und das Ergebnis dann wiederum diese Eigenschaft hat! |f(x)| <= |x| dann g(|x|) <= |x| Man koennte immerhin noch erlauben |f(x)| <= |x| + 1 denn dann ist |g(t,y)| <= |t| + |y| und somit |h(t,y)| <= |y| Die Frage ist: wie kann man Funktionen, die die Laenge nicht, oder hoechstens um Eins erhoehen durch syntaktische Methoden auszeichnen ohne einerseits semantische Information einbringen zu muessen, wie bei Cobham und andererseits ohne ueber Gebuehr restriktiv zu werden. LFPL ist eine funktionale Programmiersprache mit Booleans, Listen, Baeumen in der die Invariante erhalten wird, dass alle definerbaren Funktionen und Terme die Laenge nicht vergroessern. Hierbei ist allerdings Laenge in einem geeigneten verallgemeinerten Sinne zu verstehen, denn sonst koennte man ja nicht einmal die Nachfolgerfunktionen S0, S1, oder das "cons" fuer Listen hinschreiben. Zwei Prinzipien spielen eine Rolle. I) Die Laenge eines Paares (oder Records) ist die Summe (nicht das Maximum) der Laengen der Komponenten. II) Es gibt einen besonderen Typ <>, der nur ein Element enthaelt, welches die Laenge Eins besitzt. (Dieser Typ ist eher symbolisch zu verstehen, so wie void in Java). Schauen wir, wie wir cons typisieren koennen: (Die Laenge einer Liste ist definiert als ihre Laenge als Liste plus die Summe der Laengen der Eintraege. Dieser Wert ist Null, wenn die Eintraege Booleans sind, aber nicht Null wenn sie selber wieder Listen sind.) cons : 'a * 'a list -> 'a list |cons(x,y)| = 1 + |x| + |y| das ist nicht <= |x|+|y|. Aber wenn wir setzen: cons : <> * 'a * 'a list -> 'a list dann haben wir |cons(d,x,y)| = 1 + |x| + |y| <= |d| + |x| + |y| da ja |d| = 1. Auf der anderen Seite ist nil : 'a list in Ordnung, da ja |nil()| <= 0 Dies fuehrt zum dritten Prinzip: III) rekursive Konstruktoren von Datentypen bekommen ein extra Argument des Typs <>. Wie sieht es mit der Komposition aus? |f(x)| <= |x| und |g(x)| <= |x|, dann auch |f(g(x))| <= |x|. Aber wenn |f(x,y)| <= |x|+|y| und |g(x)| <= |x| und |h(x)| <= |x|, dann ist |f(g(x),h(x))| <= 2.|x| !!! Andererseits |f(g(x), h(y))| <= |x| + |y| Dies fuehrt zum Prinzip IV) Variablen duerfen in einem Term hoechstens einmal vorkommen. (Linearitaet). Analogie: f : V*V -> V bilineare Abbildung g(v) = f(v,v) ist keine lineare Abbildung. Ausnahme von IV. Variablen eines Typs, dessen Elemente Laenge 0 haben duerfen mehrmals benutzt werden. Z.B. bool, aber nicht <>. Woher kommen Werte des Typs <>: Antwort Pattern-Matching. Falls l : 'a list und g : 'b und h(d,x,y) : 'b dann match l with nil -> g | cons(d,x,y) -> h(d,x,y) : 'b Hierbei duerfen l, g, h auch noch andere Variablen enthalten (wie in ML oder Java). Allerdings (Linearitaetsprinzip!) duerfen weder l und g, noch l und h Variablen gemeinsam haben. g und h schon, denn es kommt ja hoechstens eins von beiden zur Anwendung. Rekursion: Wir erlauben zunaechst beliebige rekursive Definitionen so, wie in C. Ein Programm besteht also aus einer Menge gegenseitig rekursiv definierter Funktionen. Definition: Sei L eine Programmiersprache mit Listen und Booleans. L erfasst eine Komplexitaetsklasse C, wenn fuer alle A <= {0,1}^* gilt: A ist in C genau dann, wenn die charakteristische Funktion von A als Term vom Typ bool list -> bool in L darstellbar ist. Theorem: LFPL mit beliebigen rekursiven Definitionen wie oben erfasst die Komplexitaetsklasse LINSPACE. Schraenken wir auf strukturelle Rekursion ein, also etwa rekursive Aufrufe nur auf kuerzeren Argumenten, so laesst sich die Laufzeit polynomial beschraenken und man erhaelt: Theorem: LFPL mit nur struktureller Rekursion erfasst die Klasse der in linearem Platz und gleichzeitig polynomieller Zeit loesbaren Probleme. Nun kann man auch hoeherstufige Funktionen betrachten, also zu Typen 'a und 'b den Typ 'a->'b der Funktionen einfuehren. Hierbei bietet es sich an, die Linearitaetsbeschraenkung auch hierauf auszudehnen; insbesondere gilt so eine Funktion schon nach ihrer ersten Anwendung als benutzt und darf dann nicht wieder verwendet werden. Theorem: LFPL mit Funktionstypen erfasst EXPTIME, LFPL mit Funktionstypen, aber nur struktureller Rekursion erfasst P. Diese und weitere Ergebnisse finden sich in meinen Arbeiten zu non-size increasing computation. A type system for bounded space and functional in-place update (Nordic J. of Comp. 2000) Linear types and non size-increasing polynomial time computation. (Information & Computation 2003) The strength of non size-increasing computation (Symp Princ. of Prog. Lang. 2002)