Skript FSK
skript.txt
—
Plain Text,
131 KB (135013 bytes)
Dateiinhalt
Skriptum zur Vorlesung "Formale Sprachen und Komplexitaet"
Martin Hofmann SS 2011
Das Skriptum dient der Orientierung und wird im Laufe der Vorlesung
u.U. erweitert und verbessert. Massgeblich ist die Literatur
(Schoening) und die Tafelanschrift.
0: Inhalt:
==========
I Formale Sprachen und Automaten:
- Chomsky Grammatiken
- Regulaere Sprachen
- Endliche Automaten
- Nichtdeterminismus
- Abschlusseigenschaften
- Kontextfreie Sprachen
- Abschlusseigenschaften
- Pumpinglemma
- Wortproblem, CYK-Algorithmus
- Kellerautomaten
- Kontextsensitive Sprachen
- Linear beschraenkte Automaten
II Berechenbarkeit:
- Turingmaschinen
- Loop Programme
- While Programme
- Church-Turing These
- Primitive Rekursion
- mu-Rekursion
- Ackermannfunktion
- Halteproblem und Unentscheidbarkeit
III Komplexitaetstheorie:
- Zeit- / Platzkomplexitaet
- Die Klasse P (polynomiale Zeit)
- Beispiele nichttrivialer Algorithmen in P
- Die Klasse NP
- Charakterisierung mithilfe von Advice
- NP Vollstaendigkeit
- Satz von Cook
- Beispiele NP vollst. Probleme
IV Logik
- Goedels Unvollstaendigkeitssatz.
Literatur:
U Schoening: Theoretische Informatik kurzgefasst. (Vorlesungslehrbuch)
Aho-Hopcroft-Ullman: Introduction to automata theory, languages, and
computation, Addison-Wesley, 1979.
************************************
*I. Formale Sprachen und Automaten.*
************************************
1 Einfuehrung und Allgemeines
=============================
1.1 Alphabete und Woerter
-------------------------
Definition: Sei Sigma eine endliche Menge. Sigma* bezeichnet die Menge
aller endlichen Woerter ueber Sigma. Das leere Wort wird mit epsilon
(manchmal auch lambda) bezeichnet.
{a,b}* = {epsilon, a, b, aa, ab, ba, bb, aaa, aab, ... }
Die Hintereinanderschreibung von Woertern bezeichnet man als
Konkatenation oder Verkettung. Sie wird (wie die Multiplikation) durch
Infixpunkt notiert, welcher auch weggelassen werden kann.
aab.bab = aabbab
Falls w = ababa und t = bbb, dann wt=abababbb
Stets gilt epsilonw=wepsilon=w
Sigma* bildet mit der Konkatenation und epsilon ein Monoid, das freie
Monoid ueber Sigma. (Frei, weil keine Gleichungen ausser den zwingend
erforderten Monoidgleichungen gelten)
Fuehrt man etwa die Gesetze ab=ba=epsilon ein, so erhaelt man ein
anderes Monoid, in dem z.B. abbb = bbabba gilt. Dieses Monoid ist zu
einem wohlbekannten Monoid isomorph. Welchem?
Gilt w=uv, so ist u ein Praefix von w und v ein Suffix von w. Das Wort
aabba hat die Praefixe epsilon, a, aa, aab, aabb, aabba.
Weitere Notation Sigma+ = Sigma* \ {epsilon}
Eine Teilmenge U von Sigma* heisst Sprache ueber Sigma. Sind U, V
Sprachen ueber demselben Alphabet, so bezeichnet UV die Sprache
UV = {uv | u:U, v:V} = {w | es ex u:U, v:V so dass w=uv}
Potenzschreibweise: w^n = wwwww...w (n Faktoren),
U^n = UUUUU...U (n Faktoren)
Die Vereinigung U u V von Sprachen U, V wird gern auch U+V
geschrieben.
Die Sprache U* besteht aus allen Woertern der Form w1w2...wk wobei
wi:U und k:N.
Bei einelementige Sprachen laesst man gern die Mengenklammern
weg. Also ist z.B. a(a+b)* die Menge aller Woerter ueber {a,b}, die
mit einem a anfangen.
1.2 Chomsky Grammatiken
-----------------------
Definition: Eine Grammatik ist ein 4-Tupel G = (V,Sigma,P,S) wobei:
V endliche Menge (Nichtterminalsymbole)
Sigma endliche Menge (Terminalsymbole, Alphabet)
P <= (V u Sigma)+ * (V u Sigma)* (Produktionen)
S:V (Startsymbol)
Die Elemente (x,y):P werden in der Regel als x->y geschrieben und
heissen Produktionen
Sei u,v : (V u Sigma)*. Wir definieren u=>v durch
u=>v <=> es ex Produktion y->y', sowie Woerter x,z so dass u=xyz und
u=>v=xy'z.
Mit =>* bezeichnen wir die reflexive, transitive Huelle von =>, d.h.
u =>* v wenn existieren w1, w2, ..., wk wobei
u=w1
w1=>w2
...
wk-1=>wk
wk=v
Spezialfall: k=1, dann einfach u=v.
Definition: Die von einer Grammatik G erzeugte Sprache L(G) <= Sigma*
ist definiert durch
L(G) = {w:Sigma* | S=>*w}
Eine Folge von Worten
S=w0, w1, w2, ..., wk=w
wobei wi=>wi+1 heisst Ableitung von w:L(G)
Beispiel einer Typ-0 Grammatik:
S -> A1QE
Z1 -> 11Z
ZE -> QE
RE -> QE
1Q -> Q1
AQ -> AZ
AQ1 -> AR
R111 -> 1R
RE -> epsilon
ZE -> epsilon
AZ -> Z
AR -> R
Beispielableitung:
A -> A1QE -> AQ1E -> AZ1E -> A11ZE -> A11QE
-> AQ11E -> AZ11E -> A1111QE -> AQ1111E -> AQ1111 1111 1111 1111E ->
AR 111 1111 1111 1111E ->
R 111 1111 1111 1111E ->
1 R 1111 1111 1111E -> 11111RE ->
11111
Die Frage, ob L(G) = {1}* ist ein bekanntes offenes Problem.
Definition:
Alle Grammatiken sind automatisch vom Typ 0.
Eine Typ-0 Grammatik ist vom Typ 1, wenn fuer jede Produktion x->y
gilt: Entweder ist |x|<=|y| oder x=S und y=epsilon. In letzterem Fall
darf S nicht auf der rechten Seite einer Produktion erscheinen.
Typ-1 Grammatiken heissen auch kontextsensitiv.
Eine Typ-1 Grammatik ist vom Typ 2, wenn fuer jede Produktion x->y
gilt x:V. Typ-2 Grammatiken heissen auch kontextfrei.
Eine Typ-2 Grammatik ist vom Typ 3, wenn fuer jede Produktion A->w
gilt: w:Sigma u SigmaV
Beispiel einer Typ-3 Grammatik:
S -> a
S -> aS
L(G) = {a^n | n:N} = a*
Beispiel einer Typ-2 Grammatik, die nicht auch Typ-3 ist:
S -> ab
S -> aSb
L(G) = {a^nb^n | n:N}
Anderes Beispiel: arithmetische Ausdruecke.
V = {E,T,F} Sigma = {+, *, (, ), a} Startsymbol E.
E -> T
E -> E + T
T -> F
T -> T * F
F -> a
F -> (E)
a*a*(a+a)+a : L(G)
Beispiel einer Typ-1 Grammatik, die nicht auch Typ-2 ist:
S -> aSBC
S -> aBC
CB -> BC
aB -> ab
bB -> bb
bC -> bc
cC -> cc
L(G) = {a^nb^nc^n | n:N}
Beispiel einer Typ-0 Grammatik, die nicht Typ-1 ist, s.o.
Bemerkung: Bei Typ-2 und Typ-3 Grammatiken kann man Produktionen der
Form A->epsilon fuer beliebige Nichtterminalsymbole erlauben, da
solche stets systematisch eliminiert werden koennen.
Beispiel: S -> bA
A -> epsilon
A -> aA
kann ersetzt werden durch
S -> bA
S -> b
A -> a
A -> aA
1.3 Backus-Naur-Form:
---------------------
Formalismus zur Abkuerzung von Typ-2 Grammatiken
Statt
A -> beta1
...
A -> betan
schreibt man
A -> beta1 | beta2 | ... | betan
Statt
A -> alpha.gamma
A -> alpha.beta.gamma
schreibt man
A -> alpha[beta]gamma
Statt
A -> alpha.gamma | alphaBgamma
B -> beta | betaB
schreibt man
A -> alpha{beta}*gamma (oder auch je nach Autor alpha{beta}gamma)
Statt
A -> alphaBgamma
B -> beta | betaB
schreibt man
A -> alpha{beta}+gamma
1.4 Wortproblem
---------------
Definition: Wortproblem. Das Wortproblem fuer eine Grammatik besteht
darin, zu gegebenem Wort w:Sigma* zu entscheiden, ob w:L(G), oder
nicht.
Satz 1: Fuer kontextsensitive Sprachen ist das Wortproblem entscheidbar,
d.h. es gibt einen Algorithmus, der bei vorgelegter Grammatik G und
Wort w entscheidet, ob w:L(G) oder nicht.
Beweis: Man erzeugt systematisch Ableitungen solange bis entweder das
gewuenschte Wort erzeugt ist, oder bis nur noch laengere Woerter
erzeugt werden.
Etwas detaillierter: In einer Ableitung eines Wortes der Laenge n
koennen nur Woerter der Laenge <=n vorkommen. Es gibt also auch nur
endlich viele Ableitungen mit diesen Woertern, die kann man alle
durchprobieren.
Noch detaillierter: Man tabuliert iterativ die Mengen T^n_i aller
Woerter der Laenge <=n, die in <=i Schritten ableitbar sind. Nachdem
jede dieser Mengen Teilmenge der endlichen Menge der Woerter der
Laenge <=n ist, muss irgendwann gelten T^n_i=T^n_i+1 (also formal: es
existiert ein i0 sodass fuer alle i>=i0 gilt: T_i=T^n_i+1=T_i0)
Beispiel: Sei n=4 und G wie in obigem Beispiel.
T^n_0 = {S}
T^n_1 = {S,aSBC,aBC}
etc pp.
1.5 Syntaxbaeume
----------------
Ableitungen in Typ-2 (oder Typ-3) Grammatiken lassen sich als Baeume
darstellen. Hierbei wird die Reihenfolge der Ersetzung gleichzeitig
vorhandener Nichtterminalsymbole verwischt.
Die auftretenden Nichtterminalsymbole befinden sich an den inneren
Knoten. Die Kinder eines inneren Knotens werden jeweils mit den
Symbolen (Terminal und Nichtterminal) beschriftet, zu denen die
Knotenbeschriftung ersetzt wird.
Beispiel: a*a*(a+a)+a (arithmetischer Ausdruck).
Zu einem Ableitungsbaum gibt es i.a. mehrere Ableitungen. Diejenige,
die immer das am weitesten links stehende Symbol ersetzt, bezeichnet
man als Linksableitung (analog Rechtsableitung).
Es kann auch vorkommen, dass ein Wort mehrere Ableitungsbaeume
gestattet:
Beispiel:
E -> E + E | E * E | (E) | a
Es war gerade der Zweck der Nichtterminalsymbole T, F diese Art der
Mehrdeutigkeit aufzuloesen.
Mehrdeutigkeiten sind nicht wuenschenswert, da die Semantik einer
Phrase haeufig ausgehend vom Ableitungsbaum definiert wird.
Syntaxanalyse: Eingabe: Wort, Ausgabe: zugehoeriger Ableitungsbaum
oder Fehlermeldung.
Syntaxanalyse kann fuer bestimmte Spezialfaelle der Typ-2 Grammatiken
(LR(1)) besonders effizient durchgefuehrt werden und es existieren
Spezialprogramme, die zu gegebener Grammatik ein Syntaxanalyseprogramm
("Parser") in C, Java, oder ML automatische erzeugen.
Definition: Eine Grammatik G heisst mehrdeutig, wenn es ein Wort
w:L(G) gibt, welches zwei verschiedene Ableitungsbaeume besitzt.
1.6 Sprachklassen
-----------------
Eine Sprache, die von einer Typ-i Grammatik erzeugt werden kann heisst
Typ-i Sprache.
Die Sprache {a^nb^n | n:N} ist Typ-2 aber nicht Typ-1
Die Sprache {a^nb^nc^n | n:N} ist Typ-3 aber nicht Typ-2
Die Sprache aller terminierenden Java Programme ist Typ-0 aber nicht
Typ-1
Eine Typ-2 Sprache heisst inhaerent mehrdeutig, wenn jede Grammatik fuer
diese Sprache mehrdeutig ist.
Inhaerente Mehrdeutigkeit ist eher eine Kuriositaet; ein Beispiel
bildet die Sprache {a^ib^jc^k | i=j oder j=k}
2. Regulaere Sprachen und endliche Automaten
============================================
2.1 Deterministische endliche Automaten
---------------------------------------
Definition: Ein deterministischer endlicher Automat (DEA) ist gegeben durch
ein 5-Tupel
M = (Z, Sigma, delta, z0, E)
wobei
- Z (Zustaende), Sigma (Alphabet) sind endliche (disjunkte) Mengen.
- delta : Z*Sigma -> Z ist die Zustandsueberfuehrungsfunktion.
- z0:Z ist der Anfangszustand
- E <= Z ist die Menge der Endzustaende.
Automaten lassen sich anschaulich durch ihren Uebergangsgraphen
darstellen. Dessen Knoten sind die Zustaende. Wenn delta(z,a)=z', so
zeichnet man eine mit a beschriftete Kante von z nach z' ein.
Beispiel:
Z = {z0, z1, z2, z3}
Sigma = {a,b}
E = {z3}
delta(z(i),x) = z(i+1) mod 4 falls x=a
delta(z(i),x) = z(i-1) mod 4 falls x=b
Man erweitert die Zustandsuebergangsfunktion auf Woerter durch
delta(z,epsilon) = z
delta(z,wx) = delta(delta(z,w),x)
Definition: Die vom Automaten M erkannte Sprache L(M) ist definiert durch
L(M) = {w:Sigma* | delta(z0,w) : E}
Im Beispiel gilt L(M) = {w | |w|a - |w|b = 3 mod 4}
Englisch: Deterministic Finite Automaton (DFA). Plural: Automata.
DEA modellieren Berechnungen, die mit endlichem Speicher
vonstatten gehen und bei denen die Eingabedaten einmal eingegeben werden,
also nicht mehrfach gelesen werden koennen. Man kann sich also
vorstellen, dass die Eingabedaten durch sequentielles Eintreten von
Ereignissen (Knopfdruck, Sensorereignis) praesentiert werden.
Beispiel: Drei Knoepfe "Schliessen" (s), "Aufmachen" (a), "Ruehren" (r). Man
konstruiere einen Automaten, der alle Woerter erkennt, in denen mit
offenem Deckel geruehrt wird.
Wir brauchen drei Zustaende: "Zu" (z0), "Auf" (z1), "Fehler" (z2).
Wir nehmen z1 als Anfangszustand und legen folgende Uebergaenge fest:
delta(z0,s) = z0
delta(z1,s) = z0
delta(z2,s) = z2
delta(z0,a) = z1
delta(z1,a) = z1
delta(z2,a) = z2
delta(z0,r) = z0
delta(z1,r) = z2
delta(z2,r) = z2
E = {z2}
Satz 2: Jede durch einen DEA erkennbare Sprache ist regulaer, also Typ
3.
Beweis: Wir nehmen o.B.d.A an, dass der Startzustand z0 spaeter nicht
mehr angenommen wird. Also delta(z,a) =/= z0 fuer alle z,a. Man kann
einen Automaten stets so umbauen, dass diese Bedingung erfuellt ist.
Wir nehmen nun die Zustaende des DEA als Nichtterminalsymbole. Das
Startsymbol ist dann der Anfangszustand.
Wenn delta(z,a) = z', so fuehren wir eine Produktion
z -> az'
ein. Ausserdem noch eine Produktion
z -> a
falls z':E.
Ist w=a1a2a3...an in L(M), so gibt es eine Zustandsfolge z0,z1,...,zn
wobei delta(z(i-1),ai) = zi und zn:E und z0=Anfangszustand.
Dann ist aber z0 => a1z1 => a1a2z2 => ... => a1a2...an-1zn-1 => a1...an
eine Ableitung von w.
Liegt umgekehrt eine Ableitung vor, so muss diese von der o.a. Form
sein und man liest den akzeptierenden Lauf im Automaten ab.
2.2 Nichtdeterministische endliche Automaten (NEA)
--------------------------------------------------
Im folgenden werden wir "Automaten" betrachten, bei denen es zu
gegebenem Zustand z und Symbol a eine (endliche) Menge moeglicher
Folgezustaende gibt. Ist z.B. delta(z,a) = {z', z''}, so soll das
folgendes bedeuten: Befindet sich der Automat im Zustand z und wird
das Symbol a gelesen, so kann er entweder in den Zustand z' oder aber
in den Zustand z'' uebergehen.
Ein Wort w gilt als akzeptiert, wenn es moeglich ist, diese
nichtdeterministischen Auswahlen bei der Abarbeitung von w so zu
treffen, dass ein Endzustand erreicht wird.
Zunaechst ein Beispiel: folgender nichtdeterministischer Automat
erkennt alle Woerter, die mit 00 enden:
delta(z0,1) = z0
delta(z0,0) = {z0,z1}
delta(z1,0) = z2
E = {z2}
Fuer diese Sprache gibt es auch einen deterministischen endlichen
Automaten, der ist aber komplizierter.
Definition: Ein nichtdeterministischer endlicher Automat (DEA) ist gegeben durch
ein 5-Tupel
M = (Z, Sigma, delta, S, E)
wobei
- Z (Zustaende), Sigma (Alphabet) sind endliche (disjunkte) Mengen.
- delta : Z*Sigma -> Pow(Z) ist die Zustandsueberfuehrungsfunktion.
- S <= Z ist die Menge der Startzustaende.
- E <= Z ist die Menge der Endzustaende.
Sei ein Wort w = a1..an gegeben. Ein Lauf M auf w ist gegeben durch
eine Zustandsfolge z0,z1,...,zn wobei z0:S und zi:delta(zi-1,ai).
Solch ein Lauf ist akzeptierend, wenn zn:E gilt. Der Automat
akzeptiert ein Wort w, wenn es einen akzeptierenden Lauf des Automaten
auf w gibt. Die Sprache L(M) des Automaten ist definiert als die Menge
aller akzeptierten Woerter.
2.3 Determinisierung von NEA
----------------------------
Satz 3: Jede von einem NEA akzeptierte Sprache ist auch
durch einen DEA akzeptierbar.
Beweis: Durch Potenzmengenkonstruktion. Sei ein NEA M=(Z_M, Sigma,
delta_M, S_M, E_M) vorgegeben. Wir konstruieren einen DEA M', dessen
Zustaende die Mengen von Zustaenden von M ist, also Z_M' =
Pow(Z_M). Als Anfangszustand waehlen wir S, die Menge der
Startzustaende, die ja nunmehr ein Element von Z_M' ist.
Die Uebergangsfunktion von M wird wie folgt festgelegt:
delta(Z,a) = {z' | es existiert Zustand z:Z sodass z':delta(z,a)}
Endzustaende von M' sind alle Zustandsmengen Z, die einen Endzustand
enthalten.
Wir moechten nun zeigen, dass L(M') = L(M).
Sei w=a1a2...an ein Wort und S=Z0,Z1,...,Zn die Folge der "Zustaende"
in M', die bei der Abarbeitung von w auftreten, also Zi =
delta(Z(i-1),ai).
Falls z0,z1,...,zn ein Lauf von M ist, also w:L(M), dann ist
zi:Zi. Dies beweist man durch Induktion ueber i. Somit ist dann auch
zn:Zn und damit Zn ein Endzustand. Es folgt L(M) <= L(M').
Nehmen wir nun umgekehrt an, dass w:L(M'), also dass ein Endzustand
zn:Zn existiert. Wir konstruieren nun sukzessive eine Folge von
Zustaenden zi:Zi, sodass schliesslich die Gesamtfolge z0,...,zn einen
akzeptierenden Lauf bildet. Ist zi bereits konstruiert, so waehlen wir
fuer z(i-1) ein Element von Z(i-1) derart dass zi:delta(z(i-1),a). Ein
solches muss es nach Definition der Uebergangsfunktion von M'
geben. Nachdem dann aber z0:S, ist klar, dass diese Folge einen
akzeptierenden Lauf bildet und somit w:L(M) gilt.
Als Beispiel konstruieren wir den DEA, der dem Beispielautomaten mit 3
Zustaenden fuer (0+1)*00 entspricht.
Weiteres Beispiel: Lk = {w:{0,1}* | das k-letzte Zeichen von w ist 0}
Ein NEA mit k+1 Zustaenden ist schnell angegeben, jedoch es gilt:
Satz 4: Jeder DEA, der die Sprache Lk erkennt hat mindestens 2^k
Zustaende.
Beweis: Sei M ein Automat mit < 2^k Zustaenden. Es gibt zwei Woerter
w1, w2 aus {0,1}^k, sodass delta(z0,w1) = delta(z0,w2). Sei nun i die
erste Position, an der sich w1 und w2 unterscheiden, also o.B.d.A.
w_1 = u0v_1
w_2 = u1v_2
wobei aber v_1 und v_2 die gleiche Laenge haben. Jetzt waehlen wir w
beliebig, so dass |v_1w|=|v_2w|=k-1 sodass also w_1w : L_k aber w_2w
nicht in L_k ist. Andererseits gilt aber delta(z0,w1w) =
delta(delta(z0,w1),w) = delta(delta(z0,w2),w)=delta(z0,w2w). Hieraus
folgt, dass L(M) nicht gleich Lk sein kann.
2.4 Aequivalenz von Typ-3 Grammatiken und Automaten
---------------------------------------------------
Wir wissen bereits, dass jedem DEA eine aequivalente Typ-3 Grammatik
zugeordnet werden kann (Satz 2). Ausserdem entspricht jedem NEA ein
DEA (Satz 3). Fuer die Aequivalenz der drei Konzepte NEA, DEA,
regulaere Sprachen genuegt es daher folgendes zu zeigen:
Satz 5: Fuer jede regulaere (Typ-3) Grammatik G gibt es einen NEA M
mit L(G)=L(M).
Beweis: Sei die Grammatik G=(V,Sigma,P,S) gegeben. Wir konstruieren
M=(Z,Sigma,delta,S',E) wie folgt:
Z = V u {X} wobei X nicht in V.
S' = {S}
E = {S,X}, falls S->epsilon
E = {X}, sonst.
delta(A,a) = {B | A->aB} u {X | A->a}
Sei w = a1..an =/= epsilon. Wenn w : L(G) vermoege einer Ableitung
S=A1 => a1A2 => a1a2A3 => ... =>a1a2...an-1An => a1...an
wobei also die Produktionen Ai->aiAi+1, sowie An->an benutzt wurden.
Es ist dann S=A1,...,An,X ein Lauf von M auf w der in E endet, somit ist
w:L(M).
Ist umgekehrt w:L(M) vermoege des Laufs S=A1...An,X, dann muss gelten
Ai->aiAi+1, sowie An->an und es ergibt sich eine Ableitung von w.
Man beachte, dass S nicht auf der rechten Seite einer Produktion
auftritt, falls S:E.
Ist epsilon:L(G) so hat man eine Produktion S->epsilon und S:E. Ist
umgekehrt epsilon:L(M), so ist X:E und wir haben eine Produktion
S->epsilon, also epsilon:L(G).
2.5 Regulaere Ausdruecke
------------------------
Sei Sigma ein Alphabet. Die regulaeren Ausdruecke ueber Sigma sind
durch die folgende BNF gegeben:
<RegExp> ::= 0 | epsilon | (<RegExp>+<RegExp>) | (<RegExp><RegExp>) | a
/* wobei a:Sigma */ | (<RegExp>)*
Statt A+B schreibt man auch A|B.
Man laesst Klammern weg unter der Massgabe, dass * staerker bindet als
die Juxtaposition und diese wiederum staerker bindet als + und dass
Juxtaposition und + nach links assoziieren.
Zum Beispiel kuerzt man (((((a)*b)a)b)(a+b) + a) zu a*bab(a+b)+a ab.
Jeder regulaere Ausdruck A bezeichnet eine Sprache L(A) ueber Sigma,
die wie folgt rekursiv definiert ist:
L(0) = 0
L(epsilon) = {epsilon}
L(a) = {a}
L(AB) = L(A)L(B)
L(A+B) = L(A) u L(B)
L(A*) = L(A)* = {w1...wn | wi:L(A), n>=0}
Beispiel: Der regulaere Ausdruck 0 + (0+1)*00 bezeichnet die Sprache
der Woerter, die mit 00 aufhoeren vereinigt mit dem Wort 0.
Satz 6: Sei A ein regulaerer Ausdruck. Die Sprache L(A) ist regulaer.
Beweis: Durch Induktion ueber A konstruieren wir einen NEA M mit
L(M) = L(A).
Fall a: A = 0 oder epsilon oder a. Das ist leicht.
Fall b: A=B+C. Seien nach Induktionsannahme MB und MC Automaten mit
L(MB)=B, L(MC)=C. Wir vereinigen die beiden Automaten disjunkt
miteinander und erhalten so einen Automaten fuer A. Etwas
detaillierter: Sei MB = (ZB,Sigma,deltaB,SB,EB) und MC =
(ZC,Sigma,deltaC,SC,EC) und o.B.d.A. seien ZB und ZC disjunkt. Der
gesuchte Automat fuer L(A) ist dann
(ZB+ZC,Sigma,deltaB+deltaC,SB+SC,EB+EC).
Fall c: A=BC. Wir moechten die Automaten in Serie schalten. Hierzu
platzieren wir zwei disjunkte Kopien von MB und MC nebeneinander,
d.h. wie im vorhergehenden Fall sind die Zustaende des neuen Automaten
die Zustaende von MB und MC zusammen. Endzustaende sind diesmal nur die
Endzustaende von MC, Anfangszustaende sind diesmal nur die
Anfangszustaende von MB. Fuer jeden a-Uebergang von einem Zustand z:ZB
in einen Zustand aus EB fuehren wir jeweils eine a-Kante von z in
jeden der Anfangszustaende von MC ein. Ist epsilon:L(B), so werden
zusaetzlich noch alle Startzustaende von MC zu Startzustaenden
erklaert.
Fall d: A=B*. Wir beginnen mit dem Automaten MB. Zunaechst fuehren wir
einen neuen Zustand ein, der sowohl Anfangs- als auch Endzustand
ist. Dadurch ist schonmal epsilon erkannt. Sodann fuehren wir fuer
jeden a-Uebergang von einem Zustand z in einen Endzustand
a-Uebergaenge von z in jeden Anfangszustand ein.
Satz 7: Sei U regulaer. Dann existiert ein regulaerer Ausdruck A mit
L(A)=U.
Beweis: Sei U=L(M), wobei M ein DEA ist. OBdA sei ZM={1,2,...,n}. Fuer i,j,k <= n
fuehren wir die folgende Sprache ein:
R(i,j,k) = {a1...al | es gibt eine Zustandsfolge i=z0,z1,...,zl=j
und fuer 1<t<l gilt zt <= k und delta(zi,ai+1)=zi+1}
In R(i,j,k) sind also alle Woerter enthalten, die, wenn im Automaten
ausgehend von i abgearbeitet nach j fuehren und ausserdem zwischendrin
nur Zustaende <= k auftreten.
Behauptung: Fuer R(i,j,k) gibt es einen regulaeren Ausdruck.
Beweis durch Induktion ueber k.
Induktionsanfang k=0. Hier ist R(i,j,k) endlich, da ueberhaupt keine
Zwischenzustaende erlaubt sind.
Induktionsschritt. Es gilt R(i,j,k+1) = R(i,j,k) +
R(i,k+1,k)R(k+1,k+1,k)*R(k+1,j,k). Hiermit folgt die Behauptung.
Nun ist aber L(M) = U_{j:E} R(z0,j,n).
Beispiel: Sei L die Sprache aller Woerter ueber {0,1}, die eine
ungerade Zahl von Einsen enthalten. Aus dem offensichtlichen DEA mit
zwei Zustaenden kann man mithilfe des Beweises des Satzes folgenden
regulaeren Ausdruck fuer L ableiten:
0*1 + 0*1(10*1 + epsilon + 0)*
Eine manchmal effizientere Konstruktion verwendet die Ardensche Regel:
Satz 8 (Ardensche Regel): Seien A, B Sprachen ueber Sigma, wobei
epsilon nicht in A. Dann hat die Gleichung X = AX+B die eindeutige
Loesung X = A*B.
Beispiel:
LE = 0.LE + 1.LO
LO = 0.LO + 1.LE + epsilon
LO = 0*(1.LE + epsilon)
LE = 0.LE + 1.(0*(1.LE + epsilon)) = (0 + 10*1)LE + 10*
Also
LE = (0+10*1)* 10*
LO = ...
Beweis der Ardenschen Regel:
Sei epsilon nicht in A. Sei X=A*B. Falls w:A*B, so ist auch w:AA*B, also auch
AA*B+B. Ist umgekehrt w:AX+B, so folgt w:X. Sei nun X eine beliebige
Loesung der Gleichung X=AX+B. Seien u1..un Woerter aus A und v:B. Wir
zeigen durch Induktion ueber n, dass w=u1...unv:X. Falls n=0, so ist
w=v:B, also w:X, da ja B<=X. Anderenfalls ist mit Induktionshypothese
u2..unv:X, somit w:AX, somit w:X, da ja AX<=X. Sei nun schliesslich
w:X beliebig. Nachdem epsilon nicht in A ist, muss entweder w:B sein,
oder aber ein Praefix aus A haben, sich also in der Form uw' schreiben
lassen mit u:A, w':X und |w'|<|w|. Induktion ueber die Wortlaenge
zeigt w':A*B und somit auch w:A*B.
2.6 Pumping Lemma
-----------------
Mit dem Pumping Lemma kann man beweisen, dass eine gegebene Sprache
nicht regulaer ist. Beginnen wir mit einem Beispiel.
Satz 9: Die Sprache L={a^nb^n | n>=1} ist nicht regulaer.
Beweis: Waere L regulaer, so gaebe es einen DEA M mit L(M)=L. Sei n
groesser als
die Zahl der Zustaende von M. Sei w=a^nb^n. Sicherlich ist
w:L, also muss gelten delta(z0,w):E. Da nun aber weniger als n Zustaende
vorhanden sind, muss schon beim Verarbeiten des a-Blockes von w' ein
Zustand zweimal angefahren worden sein, d.h. es existieren i<j <= n mit
delta(z0,a^i) = z1
delta(z1,a^j)) = z2
delta(z2,a^(n-j+i)b^n) : E
Wir setzen jetzt w_k := a^(n-d+kd)b^n wobei d=j-i und k>=0.
Es gilt delta(z0,w_k)=delta(z0,w):F, somit werden alle w_k von M
akzeptiert, andererseits sind aber w_0, w_2, w_3, ... nicht in L,
weswegen also L(M) nicht gleich L sein kann. Damit ist gezeigt, dass
kein DEA die Sprache L erkennen kann. W.z.b.w.
Intuitiv ist klar, dass L nicht regulaer sein kann; ein DEA hat ja nur
einen endlichen Speicher; um zu testen, ob ein gegebenes Wort in L
ist, muss man sich aber die potentiell unbeschraenkte Zahl der a's
merken, die bis zum ersten b gegeben wurden.
Das Pumping Lemma verpackt diese Argumentationsweise in eine allgemein
verwendbare Form:
Satz 10 (Pumping Lemma): Sei L regulaere Sprache. Dann existiert eine
Zahl n:N mit der folgenden Eigenschaft:
Fuer alle Woerter w:L mit |w|>=n gibt es eine Zerlegung w=uxv so dass
|ux|<=n und fuer alle k>=0 ist ux^kv:L
Beweis: Sei L regulaer und folglich M ein DEA fuer L. Sei weiter n
eine natuerliche Zahl groesser als die Zustandszahl von M. Wir
behaupten, dass mit dieser Wahl von n die Aussagen des Pumping Lemma
erfuellt werden koennen. Sei hierfuer also w:L. Bei der Abarbeitung
der ersten n Buchstaben von w muss ein Zustand, sagen wir z1, doppelt
verwendet werden. Wir koennen also w zerlegen als w=uxv mit |ux|<=n,
sodass
delta(z0,u)=z1
delta(z1,x)=z1
delta(z1,v):E
Hiermit folgt aber, dass auch delta(z0,ux^kv)=delta(z1,v):E, somit
ux^kv:L, w.z.b.w.
2.7 Aequivalenzrelationen und Minimalautomaten
----------------------------------------------
Sei ein DEA M=(Z,Sigma,delta,z0,E) gegeben. Wir definieren eine
Aequivalenzrelation R_M auf Sigma* wie folgt:
w1 R_M w2 <==> delta(z0,w1) = delta(z0,w2)
Es gelten also zwei Woerter als gleich, wenn der Automat sie nicht
voneinander unterscheiden kann. Insbesondere gilt:
Beobachtung: Falls w1 R_M w2, so gilt fuer alle v:Sigma*:
w1v : L(M) genau dann wenn w2v : L(M)
Weiterhin kann man beobachten, dass die Aequivalenzklassen dieser
Relation in 1-1 Beziehung zu den von z0 aus erreichbaren Zustaenden
des Automaten sind: ist z:Z, so bildet man die Aequivalenzklasse k_z =
{w | delta(z0,w)=z}. Diese Menge ist nichtleer genau dann wenn z
erreichbar ist. Hat man umgekehrt eine Aequivalenzklasse durch
einen Repraesentanten w gegeben, so assoziiert man den Zustand
delta(z0,w). Dieser Zustand ist von der Wahl des Repraesentanten
unabhaengig.
Es liegt nun nahe, die erste Beobachtung zur Definition zu erheben:
Definition: Sei L <= Sigma* eine beliebige Sprache. Die mit L
assoziierte Aequivalenz R_L<=Sigma* x Sigma* ist wie folgt definiert:
w1 R_L w2 <==> fuer alle v:Sigma*.w1v:L <=> w2v:L
Die obige Beobachtung impliziert nun den folgenden Satz:
Satz 11: Sei M DEA und L=L(M) die von M erkannte regulaere
Sprache. Die Aequivalenz R_M ist feiner als R_L.
Es gilt R_M <= R_L, also w1 R_M w2 => w1 R_L w2.
Gilt fuer Aequivalenzrelationen R1 und R2 dass R1 <= R2, so sind die
Aequivalenzklassen von R2 Vereinigungen von Aequivalenzklassen von
R1. Daraus ergibt sich
Satz 12: Eine Sprache L <= Sigma* ist genau dann regulaer, wenn die
Aequivalenz R_L endlich viele Aequivalenzklassen hat.
Beweis: Ist L regulaer, so gibt es einen DEA M fuer L, der endlich
viele Zustaende hat. Diese Zustaende sind aber (bis auf Isomorphie)
gerade die Aequivalenzklassen von R_M. Letztere Relation hat also auch
endlich viele Aequivalenzklassen. Nach dem R_L eine Vergroeberung von
R_M ist, folgt insbesondere, dass auch R_L endlich viele
Aequivalenzklassen hat.
Hat umgekehrt R_L endlich viele Aequivalenzklassen, so kann man diese
als Zustaende eines Automaten nehmen: Wir definieren einen DEA M durch
M = (Sigma* / R_L, Sigma, delta, [epsilon], E)
wobei delta([w], a) = [wa]
und E = { [w] | w:L}
Wir schreiben hier [w] fuer die Aequivalenzklasse des Wortes w.
Hierzu ein paar Anmerkungen:
1) Es gilt w1 R_L w2 ==> w1a R_L w2a, somit ist delta
auf Aequivalenzklassen wohldefiniert.
2) Es gilt w1 R_L w2 ==> w1:L<=>w2:L, somit ist die Menge E der
Endzustaende wohldefiniert.
Nun sieht man sofort durch Induktion ueber |v|, dass delta([u],v) =
[uv] und somit delta(z0,w) = [w]. Damit folgt L(M)=L. QED
Hat eine Aequivalenzrelation endlich viele Aequivalenzklassen, so sagt
man auch, sie sei von endlichem Index.
Der im Beweis verwendete Aequivalenzklassenautomat fuer eine regulaere
Sprache L hat die minimale Zustandszahl unter allen Automaten M mit
L(M)=L, da ja seine Zustaende Vereinigungen von Aequivalenzklassen von
R_M, also Verschmelzungen von Zustaenden von M sind.
Mit folgendem Algorithmus kann man ausgehend von einem DEA M den
Aequivalenzklassenautomaten M' fuer L(M) berechnen.
Zustaende, die nicht erreichbar sind, entfernen.
Aequivalente Zustaende verschmelzen. Hierbei sind zwei Zustaende z1, z2
aequivalent, wenn gilt
delta(z1,w):E <==> delta(z2,w):E
Um dies effektiv auszurechnen, betrachtet man stattdessen die
Inaequivalenz: Zwei Zustaende z1, z2 werden auseinandergehalten,
i.Z. z1 # z2, wenn eine der folgenden Bedingungen erfuellt ist:
*) z1:E und z2 nicht in E,
*) z1 nicht in E und z2 in E,
*) es existiert a:Sigma, sodass delta(z1,a)#delta(z2,a).
Legt man nun eine Tabelle an mit einem Eintrag fuer jedes Zustandspaar
(z1,z2), so kann man durch sukzessives Anwenden der drei Regeln alle
Paare (z1,z2) markieren, fuer die gilt z1#z2.
Alle Zustandspaare, die nicht markiert worden sind, koennen nunmehr
verschmolzen werden. Aufgrund der ersten beiden Regeln wird niemals
ein End- mit einem Nichtendzustand verschmolzen.
2.8 Abschlusseigenschaften
--------------------------
Satz 13: Sind A, B regulaere Sprachen ueber einem Alphabet Sigma, so sind
auch die folgenden Sprachen regulaer:
1) A + B (Vereinigung)
2) AB (Konkatenation)
3) A*
4) Sigma* \ A (Komplement)
5) A geschnitten mit B
6) A \ B
Beweis:
1,2,3) Dies wurde schon im Beweis von Satz 6 gezeigt: Aus NEA's
fuer A und B konstruiert man NEA's fuer die unter 1, 2, 3 genannten
Sprachen.
4) Um einen Automaten fuer Sigma* \ A zu erhalten geht man von
einem DEA M=(Z,Sigma,delta,z0,E) fuer A aus. Nun ist aber
M'=(Z,Sigma,delta,z0,Z\E) ein Automat fuer Sigma*\A, da ja alle Woerter aus
Sigma*\A in einen Nicht-Endzustand, also einen Zustand in Z\E
fuehren. Man beachte, dass dies nur bei deterministischen Automaten
funktioniert. Will man also eine durch einen NEA gegebene Sprache
komplementieren, so muss der NEA zunaechst determinisiert werden.
5) Dies folgt aus 1, 4 mit dem de Morganschen Gesetz A geschnitten B =
~(~A+~B). Alternativ kann aus NEA M1=(Z1,Sigma,delta1,S1,E1) und
M2=(Z2,Sigma,delta2,S2,E2) ein NEA M3 fuer A geschnitten mit B
wie folgt konstruiert werden: M3=(Z1*Z2,Sigma,delta3,S1*S2,E1*E2)
wobei delta3((z1,z2),a) = delta3(z1,a)*delta3(z2,a). Es gibt also
eine mit a beschriftete Kante von (z1,z2) nach (z1',z2'), wenn
z1-a->z1' und z2-a->z2'.
6) Dies folgt aus 4,5.
2.9 Entscheidbarkeitsfragen
---------------------------
Die folgenden Probleme sind entscheidbar, d.h. es existieren
Algorithmen.
1) Leerheitsproblem: Sei M ein NEA. Ist L(M)=0?
2) Aequivalenzproblem: Seien M1, M2 NEA. Ist L(M1)=L(M2)?
3) Aequivalenzproblem fuer regulaere Ausdruecke: Seien A1, A2
regulaere Ausdruecke. Ist L(A1)=L(A2)?
4) Universalitaetsproblem: Sei M ein NEA: Ist L(M)=Sigma*?
3. Kontextfreie Sprachen
========================
Wdh.: Typ-2 Grammatik (= kontextfreie Grammatik):
Chomsky Grammatik so dass:
1) Alle Produktionen sind von der Form
X -> alpha
wobei alpha : (V u Sigma)*
2) Hat man eine Produktion X -> epsilon, so muss gelten X=S und ausserdem darf dann
S nicht auf den rechten Seiten auftauchen.
Eine Grammatik, die der Bedingung 1 genuegt kann in eine aequivalente
kontextfreie Grammatik ueberfuehrt werden. Hierzu bestimmt man
systematisch die Menge V1 aller Nichtterminalsymbole X fuer die gilt X->*
epsilon. Fuer jede Produktion Y->alphaXbeta mit X:V1 fuehrt man dann
eine zusaetzliche Produktion Y->alphabeta ein. Anschliessend kann man
alle Produktionen der Form X->epsilon entfernen und hoechstens, falls
epsilon:L(G), eine Produktion S->epsilon einfuehren.
Typisches Beispiel einer kontextfreien Grammatik:
V = {E,T,F} Sigma = {+, *, (, ), a} Startsymbol E.
E -> T
E -> E + T
T -> F
T -> T * F
F -> a
F -> (E)
a*a*(a+a)+a : L(G)
3.1: Chomsky Normalform:
------------------------
Def.: Eine Typ-2 Grammatik G mit epsilon nicht in L(G) ist in Chomsky
Normalform, wenn jede Produktion eine der folgenden beiden Formen
besitzt:
1) X -> YZ
2) X -> a
wobei X,Y,Z:V und a:Sigma.
Satz 14: Zu jeder Typ-2 Grammatik G mit epsilon nicht in L(G) existiert
eine Grammatik G' in Chomsky NF mit L(G)=L(G').
Beweis:
1.) Eliminieren von Produktionen der Form X->Y
2.) Einfuehren kuenstlicher Nichtterminalsymbole, dadurch erhalten alle Produktionen die Form 1) oder 2'): X->Y1Y2...Yl.
3.) Durch weiteres Einfuehren zusaetzlicher NT erhaelt man die CNF.
Beispiel: S->AB, A->ab|aAb, B->c|cB
In CNF: S->AB, A->CD|CF, B->c|EB, C->a
3.2 Pumping Lemma
-----------------
Satz 15: Pumping Lemma: Sei L eine Typ-2 Sprache. Dann existiert eine
Zahl n:N, die Pumpingzahl zu L, sodass jedes Wort z:L mit |z| >= n
eine Zerlegung der Form z = uvwxy mit den folgenden Eigenschaften
gestattet:
*) |vx| >= 1
*) |vwx| <= n
*) Fuer alle i>=0 gilt: uv^iwx^iy : L
Beweis: Sei G eine Grammatik in CNF mit L(G)=L und sei m die Zahl der
Nichtterminalsymbole von G. Wir setzen n = 2^m. Sei z ein Wort in L
mit |z| >= 2^m = n. Ein Ableitungsbaum von z hat |z| also >= 2^m
Blaetter, wobei hier ein Blatt aus einer (1-Schritt) Ableitung X->a
besteht, sodass sich in den Blaettern jeweils ein Nichtterminal- und
ein Terminalsymbol befindet.
Daher muss es einen Pfad der Laenge mindestens m von S zu einem
solchen Blatt geben, auf welchem sich also mindestens m+1
Nichtterminalsymbole befinden muessen. Beispiel: S->X2->X3->a ist ein
Pfad der Laenge 2, auf dem sich 3 Nichtterminalsymbole
befinden.
Nachdem es nur m Nichtterminalsymbole gibt, muss auf diesem Pfad
mindestens ein Symbol doppelt auftreten. Sei X dieses Symbol. Man hat
also Ableitungen S =>* uXy, X =>* vXx, X=>*w, wobei z=uvwxy und
|vx|>=1. Waehlt man X als die erste Wdh eines Nichtterminalsymbols
von unten gesehen, so gilt |uwx|<=n. Es ist nun aber klar, dass auch
uv^iwx^iy fuer alle i>=0 herleitbar sind. QED
Anwendungsbeispiel: Die Sprache L = {a^nb^nc^n | n>= 0} ist nicht
kontextfrei. Falls doch, so gaebe es die Pumpinglemmazahl n. Waehlt
man z=a^nb^nc^n, so bekommt man eine Zerlegung z=uvwxy mit
|vwx|<=n. Daher sind in vwx nicht alle drei Buchstaben a,b,c,
vorhanden. Ein Aufpumpen wird daher die Balance der drei
Buchstabenarten zerstoeren und Woerter produzieren, die nicht in der
Sprache L sind. Ein Widerspruch.
Satz 16: Eine Typ-2 Sprache L ueber einelementigem Alphabet {a} ist regulaer.
Beweis: Siehe Schoening.
Man beachte, dass ein Wort ueber einelementigem Alphabet
nichts anderes als eine natuerliche Zahl ist.
Sei n die Pumpingzahl zu L. Ist a^m:L, so gibt es eine Zerlegung m
= k+l sodass auch a^(k+il) : L fuer alle i.
3.3 Abschlusseigenschaften, siehe unten
---------------------------------------
3.4 Der CYK Algorithmus
-----------------------
Benannt nach den Erstbeschreibern Cocke-Younger-Kasami.
Sei G = (V,Sigma,P,S) eine Typ-2 Grammatik in Chomsky Normalform. Um
festzustellen, ob ein gegebenenes Wort w in L(G) liegt, kann man
folgendes rekursives Verfahren probieren:
Fuer i<=j<=|w| und X:V definieren wir
| true, falls X ->* w_i,...,w_j
Abl(X,i,j) = <
| false, sonst
Klarerweise ist w:L(G), falls Abl(S,1,|w|) = true. Die Funktion Abl
kann nun wie folgt rekursiv definiert werden:
Fall i=j:
Es ist Abl(X,i,j) = true genau dann wenn die Produktion X=>w_i in P
vorhanden ist.
Fall i<j:
Es ist Abl(X,i,j) = true genau dann wenn es eine Produktion X => YZ
gibt und ausserdem ein Index k mit i<=k<j existiert, sodass Abl(Y,i,k)
und Abl(Z,k+1,j) gilt.
Es gibt nun insgesamt nur O(|V|*|w|*|w|) viele moegliche Aufrufe der
Funktion Abl, sodass es sich wieder (wie schon bei der Berechnung
eines regulaeren Ausdrucks aus einem DEA) anbietet,
bereits berechnete Abl-Werte in einer Merktabelle abzuspeichern und
aus dieser bei abermaliger Verwendung abzurufen. Hierdurch wird die
Rechenzeit auch auf O(|V|*|n|*|n|) abgesenkt.
Eine besonders effiziente Version fuellt die Merktafel ohne jede
Rekursion gleich iterativ von unten aus; das ist der CYK Algorithmus
benant nach seinen Entdeckern Cocke, Younger und Kasami.
CYK Algorithmus:
Eingabe: eine Grammatik G = (V,Sigma,P,S) in CNF und ein Wort w.
Ausgabe: true, falls w:L(G), false sonst.
Sei n = |w|.
Lege ein Array T der Groesse n^2 an, dessen Eintraege Mengen (oder
Listen) von Nichtterminalsymbolen sind.
Initialisiere T[i,j] = {} fuer i,j=1..n.
Fuer i = 1..n
Setze T[i,i] = {X | X->w_i in P}
Fuer d=1..n-1
Fuer i=1..n-d
Setze j = i+d
Setze T[i,j] = {X | es existiert k mit i<=k<j und
Y in T[i,k] und
Z in T[k+1,j] mit X=>YZ in P}
Falls S:T[1,n]: Ausgabe true
Ansonsten: Ausgabe false.
Beispiel aus Wikipedia:
Sei G die folgende Grammatik:
S->AB|BC, A->BA|a, B->CC|b, C->AB|a
Ausserdem w = bbabaaa.
------ j ------>
b b a b a a a
1 2 3 4 5 6 7
| b 1 B - A S,C B S,A B
| b 2 B S,A S,C B S,A B
| a 3 A,C S,C B S,A B
i b 4 B S,A - S,A,C
| a 5 A,C B S,A,C
V a 6 A,C B
a 7 A,C
Man liest ab: w ist nicht in L, aber B =>* w. Ausserdem gilt
S =>* bbabaa.
3.5 Kellerautomaten
-------------------
Das den Typ-2 Grammatiken (und Sprachen) entsprechende Automatenmodell
ist der Kellerautomat. Ein solcher hat zusaetzlich zum beschraenkten
(von der Eingabelaenge unabhaengigen) Speicher eines DEA oder NEA
einen unbeschraenkten Keller zur Verfuegung auf dem er nach Massgabe
der Eingabe und des Zustands schreiben und lesen kann. Wie bei Kellern
ueblich, darf nur das oberste Kellersymbol gelesen werden.
Wie die endlichen Automaten sind die Kellerautomaten im allgemeinen
nichtdeterministisch.
Definition: Ein Kellerautomat (PDA) ist ein Sextupel
M=(Z,Sigma,Gamma,delta,z0,#) wobei folgendes gilt:
Z, Sigma, Gamma sind endliche Mengen
Z ist die Menge der Zustaende
z0:Z ist der Anfangszustand
Sigma ist das Eingabealphabet (der Automat erkennt Woerter ueber
Sigma)
Gamma ist das Kelleralphabet (die Symbole aus Gamma koennen auf dem
Keller abgelegt werden)
delta : Z * (Sigma u {epsilon}) * Gamma -> Pfin(Z * Gamma*)
ist die Uebergangsrelation. Hierbei ist Pfin(X) die Menge der
endlichen Teilmengen der Menge X.
# : Gamma ist der initiale Kellerinhalt.
Intuitiv bedeutet (z',alpha) : delta(z,a,X), dass der Automat im
Zustand z, bei oberstem Kellersymbol X und bei naechstem Eingabesymbol
a die Moeglichkeit hat, in den Zustand z' ueberzugehen und das oberste
Kellersymbol X durch das Wort alpha zu ersetzen. Ist dagegen
(z',alpha) : delta(z,epsilon,X), so bedeutet das, dass bei oberstem
Kellersymbol X und Zustand z spontan in den Zustand z' uebergegangen
werden kann wobei gleichzeitig das Symbol X durch alpha ersetz wird.
Zu Beginn enthaelt der Keller nur das Symbol #; ist der Keller leer
und gleichzeitig die Eingabe aufgebraucht, so gilt die Eingabe als
akzeptiert. Kann kein weiterer Uebergang getaetigt werden, oder ist
die Eingabe aufgebraucht ohne dass der Keller leer ist, so gilt die
Eingabe als verworfen. Die erkannte Sprache L(M) ist die Menge aller
Woerter, fuer die es einen akzeptierenden Lauf des Automaten
gibt. Dies wollen wir nunmehr formalisieren.
Definition. Sei M=(Z,Sigma,Gamma,delta,z0,#) ein PDA. Eine
Konfiguration ist ein Tripel (z,w,alpha), wobei z:Z, w:Sigma*,
alpha:Gamma*. Die binaere Relation |- auf Konfigurationen wird wie
folgt definiert:
(z,w,gamma) |- (z',w',gamma') <====> es existieren
a:Sigma u {epsilon},
alpha : Gamma*,
X : Gamma,
beta : Gamma*
sodass
(z',alpha) : delta(z,a,X) und
w = aw', gamma = Xbeta, gamma'=alpha.beta
Nun definieren wir
L(M) = {w | (z0,w,#) |-* (z,epsilon,epsilon) fuer ein z:Z}
Ende der Definition.
Intuitiv beschreibt eine Konfiguration (z,w,gamma)
den momentanen globalen Zustand
des PDA durch den Zustand z seiner endlichen Kontrolleinheit, die
verbleibende Eingabe w und den Inhalt seines Kellers gamma.
Der PDA akzeptiert ein Wort, wenn er ausgehend von der zu diesem Wort
gehoerenden Anfangskonfiguration den leeren Keller erreicht und dabei
die Eingabe ganz verarbeitet.
Satz 19: Sei G=(V,Sigma,P,S) eine Typ-2 Grammatik. Es existiert ein
PDA M = (Z,Sigma,Gamma,delta,z0,#) mit L(M)=L(G).
Beweis: Wir waehlen Z={z0} alos nur ein Zustand und Gamma = Sigma u
V. Nunmehr setzen wir
delta(z0,epsilon,X) = {(z0,alpha) | X->alpha : P}
delta(z0,a,b) = if a=b then {(z0,epsilon)} else {}
# = S
Man zeigt nun leicht, dass L(M) = L(G) unter Verwendung der folgenden
Invariante: von der Konfiguration (z0,w,alpha) kann der Automat
akzeptieren genau dann, wenn alpha =>* w.
QED
Wir wollen uns die Funktionsweise des Kellerautomaten noch einmal
intuitiv veranschaulichen.
Zu Beginn legen wir also Startsymbol S in den Keller.
Solange der Keller nicht leer ist, tun wir folgendes:
Ist das oberste Kellersymbol ein Nichtterminalsymbol X, so waehlen wir
(nichtdeterministisch) eine Produktion X->alpha und ersetzen X durch
alpha (man entfernt X und legt dann der Reihe nach die Symbole von
alpha in den Keller).
Ist das oberste Kellersymbol ein Terminalsymbol, so wird das naechste
Eingabezeichen gelesen. Stimmt es mit diesem ueberein, so wird es
entfernt. Stimmt es nicht ueberein, so wird die Eingabe verworfen.
Ist der Keller leer und gleichzeitig die Eingabe aufgebraucht, so ist
diese akzeptiert. In allen anderen Faellen wird die Eingabe verworfen.
Beispiel: S -> ab|aSb
Eingabe aaabbb.
Kellerinhalt noch zu verarbeitende Eingabe
S aaabbb
aSb aaabbb
Sb aabbb
aSbb aabbb
Sbb abbb
abbb abbb
bbb bbb
bb bb
b b
Der Keller ist leer; die Eingabe auch: Die Eingabe
wird akzeptiert. Natuerlich haette bei weniger geschickter Wahl der
nichtdeterministischen Entscheidungen die Eingabe auch
verworfen werden koennen. Wie bei den NEA gilt aber eine Eingabe als
vom Automaten akzeptiert, wenn es einen akzeptierenden Lauf gibt.
In diesem Fall koennte auch ein deterministischer Kellerautomat die
Sprache erkennen: man liest einfach von der Eingabe a's und packt sie
in den Keller. Wenn dann b's kommen, so entfernt man vom Keller
entsprechend die a's. Es gibt aber Typ-2 Sprachen, die nicht durch
einen deterministischen Kellerautomaten erkannt werden koennen.
Satz 20: Sei M=(Z,Sigma,Gamma,delta,z0,#) ein PDA. Es existiert eine
Typ-2 Grammatik mit L(G)=L(M).
Beweis: Wir koennen o.B.d.A. annehmen, dass (z',alpha):delta(z,a,X)
impliziert |alpha|<=2.
Fuer z,z':Z und X:Gamma definieren wir
L(z,X,z') = {w:Sigma* | (z,w,X) |-* (z',epsilon,epsilon)}
Die so definierte Sprache L(z,z',X) besteht also aus allen Woertern,
die der Automat ausgehend vom Zustand z und Kellerinhalt X akzeptiert
mit der zusaetzlichen Massgabe, dass am Ende neben dem leeren Keller
der Zustand z' erreicht ist.
Es gilt L(M) = U_(z:Z) L(z0,#,z). Die Sprachen L(z,X,z') erfuellen aber eine
Rekurrenz, die sich unmittelbar in eine Typ-2 Grammatik uebersetzen
laesst:
L(z,X,z') = {a | (z',epsilon):delta(z,a,X)} +
{aw | (z1,Y):delta(z,a,X), w:L(z1,Y,z')} +
{aw1w2 | (z1,YZ):delta(z,a,X), w1:L(z1,Y,z2), w2:L(z2,Z,z')}
In allen Klauseln ist a:Sigma u {epsilon}.
Zur letzten Klausel: Um YZ vom Keller wegzukriegen muss zunaechst Y
und anschliessend Z entfernt werden.
Aus dieser Definition ergibt sich unmittelbar, dass alle L(z,X,z')
kontextfrei sind. Hier ist der Vollstaendigkeit halber eine
Grammatik. Als Nichtterminalsymbole waehlen wir die L(z,X,z') und
zusaetzlich ein Startsymbol S. Die Produktionen sind wie folgt:
S -> L(z0,#,z) fuer jeden z:Z.
L(z,X,z') -> a fuer alle a sodass (z',epsilon):delta(a,z).
L(z,X,z') -> aL(z1,Y,z') fuer alle a,z1,Y mit (z1,Y):delta(a,z).
L(z,X,z') -> aL(z1,Y,z2)L(z2,Z,z') fuer alle a,z1,z2,Y,Z mit (z1,YZ):delta(a,z)
QED
3.3 Abschlusseigenschaften
--------------------------
Satz 17: Seien A, B kontextfreie Sprachen. Es sind auch A u B, AB, A*
kontextfreie Sprachen.
Beweis: Durch explizite Angabe von Grammatiken (leicht).
Satz 18: Die kontextfreien Sprachen sind weder unter Durchschnitt,
noch unter Komplement abgeschlossen.
Beweis: Seien L1 = {a^ib^jc^j | i,j>0}, L2 = {a^ib^ic^j | i,j>0}. Wir
wissen, dass L1 geschnitten mit L2 nicht kontextfrei ist. Andererseits
sieht man leicht, dass L1 und L2 fuer sich genommen kontextfrei sind.
Somit sind die Typ-2 Sprachen also nicht unter Durchschnitt
abgeschlossen. Nun ist aber der Durchschnitt aus Vereinigung und
Komplement definierbar mithilfe der de Morgan'schen Regel. Da aber die
kontextfreien Sprachen unter Vereinigung abgeschlossen sind, koennen
sie nicht gleichzeitig auch unter Komplement abgeschlossen sein.
Wir bemerken noch, dass diejenigen Sprachen, die von deterministischen
Kellerautomaten erkannt werden, das sind die deterministischen
kontextfreien Sprachen, unter Komplement abgeschlossen sind (wie das
in der Regel bei deterministischen Automaten der Fall ist) und in den
Typ-2 Sprachen echt enthalten sind. Z.B. ist die Sprache der
Palindrome nicht deterministisch kontextfrei.
Deterministisch kontextfreie Sprachen sind praktisch relevant, da ein
deterministischer Kellerautomat ein effizientes Erkennungsverfahren
bietet (lineare Laufzeit im Gegensatz zur kubischen Laufzeit des CYK
Algorithmus).
Gern werden die erforderlichen deterministischen Kellerautomaten dann
in der LR(k)-Form praesentiert. Hierbei geht man vom
nichtdeterministischen Kellerautomaten aus und stattet diesen mit
einer zusaetzlichen Steuerungseinheit aus, die aufgrund des
Kellerinhalts und der k naechsten Eingabesymbole (k lookahead)
ermittelt, welche Produktion zu waehlen ist. Diese Steuerungseinheit
besteht selbst wiederum aus einem DEA, der auf dem Kellerinhalt
operiert. Details im Compilerpraktikum.
4. Kontextsensitive und Typ-0 Sprachen
======================================
Ein Automatenmodell fuer Typ 1 Sprachen muss noch
allgemeiner als die PDA sein. Es bietet sich an, gleich das
Automatenmodell fuer die Typ-0 Sprachen, naemlich die Turingmaschine
vorzustellen und dann ein Automatenmodell fuer Typ-1 als
Einschraenkung letzterer zu formulieren.
4.1 Turingmaschinen
-------------------
Eine Turingmaschine (kurz TM) kann als endlicher Automat mit
zusaetzlichem unbegrenzten Schreib-Lese-Speicher verstanden werden,
der also nicht wie beim PDA einer besonderen Zugriffsdisziplin
unterworfen ist.
Man formalisiert das durch ein unendliches Band, dessen Felder aber
bis auf endlich viele ein Leerzeichen enthalten. Auf diesem Band
operiert ein Schreib-Lese-Kopf, der durch eine endliche
Kontrolleinheit gesteuert wird. Nach Massgabe des internen (endlichen)
Zustands und des Bandinhalts unter dem Schreib-Lese-Kopf kann dann
dieser Bandinhalt ueberschrieben werden, eine Zustandsaenderung
herbeigefuehrt werden und der Schreib-Lese-Kopf nach links oder rechts
bewegt werden, bzw auch an Ort und Stelle verbleiben.
Definition: Eine Turingmaschine ist ein Septupel M =
(Z,Sigma,Gamma,delta,z0,[],E), wobei folgendes gilt:
* Z ist eine endliche Menge, die Zustandsmenge
* Sigma ist eine endliche Menge, das Eingabealphabet
* Gamma ist eine endliche Menge, das Bandalphabet. Letzteres muss eine
Obermenge von Sigma sein.
* z0:Z ist der Anfangszustand.
* []:Gamma ist das Leerzeichen. Das Leerzeichen darf kein Element von
Sigma sein.
* E <= Z ist die Menge der Endzustaende.
* delta : Z * Gamma -> Pow(Z * Gamma * {L,R,N}) ist die
Zustanddsueberfuehrungsfunktion.
Eine Konfiguration einer Turingmaschine ist ein Tripel k =
(wl,z,wr). Hierbei bezeichnet kl den Bandinhalt links des
Schreib-Lese-Kopfes ausschliesslich der gerade besuchten Position und
wr den Bandinhalt rechts des Schreiblesekopfes einschliesslich der
gerade besuchten Position. Falls (o.B.d.A) Z und Gamma disjunkt sind,
schreibt man gerne k=wlzwr. Das Wort wr darf hierbei nicht leer sein.
Die zweistellige Relation |- auf der Menge der Konfigurationen ist
erklaert durch:
/ (a1..am,z',c b2..bn), falls
| (z',c,N):delta(z,b1), m>=0,n>=1
|
| (a1..am c,z',b2..bn), falls
(a1..am,z,b1..bn) |- | (z',c,R):delta(z,b1), m>=0,n>=2
|
| (a1..am-1,z',am c b2..bn), falls
| (z',c,L):delta(z,b1), m>=1,n>=1
\
Ausserdem gibt es noch die folgenden beiden Sonderfaelle:
a1..amzb1 |- a1..amcz'[], falls (z',c,R):delta(z,b1)
zb1..bn |- z'[]cb2..bn, falls (z',c,L):delta(z,b1)
Sie beschreiben, dass sich links von den a's und rechts von den b's
Leerzeichen befinden.
Definition: Eine Turingmaschine ist deterministisch, wenn |delta(z,b)|
= 1 fuer alle z:Z, b:Gamma. In diesem Falle schreibt man auch
delta(z,b) = (z',c,D) statt delta(z,b) = {(z',c,D)}.
Beispiel: Folgende Turingmaschine interpretiert eine Eingabe ueber
Sigma={0,1} als Binaerzahl und addiert 1 hinzu.
M = ({z0,z1,z2,ze},{0,1},{0,1,[]},delta,z0,[],{ze}).
wobei
delta(z0,0) = (z0,0,R)
delta(z0,1) = (z0,1,R)
delta(z0,[]) = (z1,[],L)
delta(z1,0) = (z2,1,L)
delta(z1,1) = (z1,0,L)
delta(z1,[]) = (ze,1,N)
delta(z2,0) = (z2,0,L)
delta(z2,1) = (z2,1,L)
delta(z2,[]) = (ze,[],R)
Es gilt zum Beispiel:
z0 101 |-* [] ze 110 []
Definition: Die von einer Turingmaschine M akzeptierte Sprache L(M)
ist definiert durch
L(M) = {w:Sigma* | z0 w |-* alpha z beta, wobei z:E}
Wir wollen nun Turingmaschinen definieren, die nicht ueber den linken
und rechten Rand der Eingabe hinausfahren, wohl aber die Eingabe
ueberschreiben duerfen. Solche Maschinen werden auch als LBA (Linear
beschraenkter Automat, linearly bounded automaton) bezeichnet. Damit
solche eine Maschine die Raender der Eingabe erkennen kann, nehmen wir
an, dass das Bandalphabet fuer jedes a:Sigma eine Kopie $a enthaelt, die
dazu dient, die Eingabe rechts abzuschliessen.
Definition: Eine (nichtdeterministische) Turingmaschine ist linear
beschraenkt, wenn es zu jedem a:Sigma eine Kopie $a in Gamma \ Sigma \
{[]} gibt, sodass fuer alle w=a1..am:Sigma* gilt:
z0 a1 ... am-1 $am |-* alpha z beta ======> |alpha beta| = m
Satz 21: Sei G eine Typ-1 Grammatik. Dann existiert ein LBA M mit L(M)=L(G).
Beweis: Der Automat (die Maschine M) ueberschreibt Teile der Eingabe
nichtdeterministisch durch Rueckwaertsanwendung von
Produktionen. Fuehrt dies zu einer Verkuerzung, so werden die weiter
rechts stehenden Bandsymbole entsprechend nach links verschoben. Die
Maschine akzeptiert, wenn der nichtleere Bandinhlat nur noch aus S
besteht.
Satz 22: Sei M ein LBA. Dann existiert eine Typ-1 Grammatik mit
L(G)=L(M).
Beweis: Wir fuehren hilfsweise das Alphabet Delta=Gamma u (Z * Gamma)
ein. Dieses erlaubt uns, eine Konfiguration k = a1..am z b1..bn von M durch
ein Wort (ueber Delta) der Laenge m+n zu beschreiben: naemlich das
Wort k~ = a1..an(z,b1)b2..bn.
Es ist nun leicht, kontextsensitive Produktionen anzugeben, die auf
der Ebene dieser Kodierung die Relation |- beschreiben in dem Sinne
dass k |-* k' genau dann wenn k~ =>* k'~: Ist naemlich
(z',b,L):delta(z,a), so fuehrt man die Produktionen
c (z,a) -> (z',c) b
fuer alle c:Gamma ein. Analog geht man fuer die delta-Uebergaenge mit
N und R vor. Die beiden "Sonderfaelle" bei denen Leerzeichen in die
Konfiguration einfliessen, koennen bei einem LBA nicht vorkommen,
muessen daher auch nicht beruecksichtigt werden.
Sei P' die so erhaltene Produktionenmenge.
Die gewuenschte Grammatik G=(V,Sigma,P,S) hat nun folgende Form:
V = {S,A} u (Delta * Sigma)
P = {S -> A ($a,a) | a:Sigma} u
A -> A (a,a) | a:Sigma} u
A -> ((z0,a),a) | a:Sigma} u
/* Hiermit werden alle Woerter der Form
((z0,a1),a1)(a2,a2)...(am-1,am-1)($am,am) fuer a1..am : Sigma* erzeugt
*/
{(X,a)(Y,b) -> (U,a)(V,b) | XY->UV : P'} u
/* Hiermit werden die Operationen von P' auf den ersten Komponenten
durchgefuehrt. Die zweiten Komponenten bleiben bestehen. */
{((z,a),b) -> b | z:E } u
{(a,b) -> b | a:Gamma, b:Sigma}
/* Hiermit werden die ersten Komponenten geloescht, vorausgesetzt dass
ein Endzustand erreicht wurde. */
Es ist klar, dass L(G)=L(M) gilt. Mit der selben Technik laesst sich
ausserdem der folgende Satz beweisen:
Satz 23: Die Typ-0 Sprachen sind genau die von Turingmaschinen
erkennbaren Sprachen.
Bemerkung: Die Unterscheidung "deterministisch" -
"nichtdeterministisch" macht bei allgemeinen Turingmaschinen keinen
Unterschied, da man alle Moeglichkeiten einer nichtdeterministischen
Turingmaschine in einer deterministischen systematisch Durchprobieren
kann. Dies fuehrt allerdings zu einem erhoehten
Ressourcenverbrauch. Insbesondere ist es ein offenes Problem (das
LBA-Problem), ob deterministische linear beschraenkte Turingmaschinen
genauso maechtig sind wie (nichtdeterministische) LBAs. Bei der naiven
Simulation eines LBA durch eine deterministische Turingmaschine faellt
ein Platzbedarf von mindestens n^2 an.
LBA-Problem: Laesst sich jede Typ-1 Sprache durch einen
deterministischen LBA erkennen, oder nicht?
Satz 24 (Immerman-Szelepcsenyi): Die kontextsensitiven Sprachen, also
die durch LBA erkennbaren Sprachen sind unter Komplement
abgeschlossen.
Der Beweis dieses Satzes ist nicht Gegenstand der Vorlesung.
Er findet sich im Schoening oder,
verstaendlicher dargestellt, in einem Buch ueber
Komplexitaetstheorie wie Bovet-Crescenzi oder Papadimitriou.
*******************************
*II. Berechenbarkeitstheorie. *
*******************************
1 Intuitive und Turing-Berechenbarkeit
======================================
Eine Funktion f : Sigma* ^n -> Sigma* (z.B. Sigma={0,1}) ist intuitiv
berechenbar, wenn es ein Rechenverfahren (Algorithmus, Javaprogramm)
gibt, welches bei Eingabe w:Sigma* ^n Rechenschritte durchfuehrt und
dann irgendwann anhaelt und das Ergebnis f(w1..wn) liefert.
Man erweitert diesen intuitiven Berechenbarkeitsbegriff auf partielle
Funktionen mit der Massgabe, dass das Rechenverfahren an solchen
Eingaben fuer die f undefiniert ist, nicht terminieren soll.
Beispiele: Die Funktion f(x,y) = x / y ist intuitiv berechenbar
aufgrund des aus der Schule bekannten Divisionsalgorithmus.
Die nirgends definierte Funktion ist berechenbar aufgrund des BASIC
Programms
10 GOTO 10
Die Funktion f(n) = 0, falls die Dezimalbruchentwicklung von pi einen
Block von n aufeinanderfolgenden 7ern enthaelt; undefiniert sonst
ist intuitiv berechenbar durch exhaustive Suche (brute force).
Die Funktion
f(n)=0, falls das LBA-Problem eine positive Loesung hat, f(n)=1,
sonst;
ist intuitiv berechenbar, da f eine konstante Funktion ist (wir wissen
nur nicht welche) und konstante Funktionen intuitiv berechenbar sind.
Die Funktion
f(n) = 0, falls die Dezimalbruchentwicklung von pi einen
Block von n aufeinanderfolgenden 7ern enthaelt; 1 sonst
ist erstaunlicherweise auch berechenbar, wobei allerdings auch hier
wiederum kein Verfahren bekannt ist. Der Grund ist folgender. Entweder
enthaelt die Dezimalbruchentwicklung von pi beliebig lange 7er
Bloecke, dann ist f konstant 0 also berechenbar. Anderenfalls gibt es
einen 7er Block einer bestimmten Maximallaenge n0 und keine 7er
Bloecke groesserer Laenge. Dann aber ist f(n)=if n<=n0 then 0 else 1
und auch diese Funktion ist intuitiv berechenbar.
Anders sieht es aus mit der Funktion
f(n) = 0, falls die Dezimalbruchentwicklung von pi einen
Block von genau n aufeinanderfolgenden 7ern enthaelt; 1 sonst
Hier ist kein Rechenverfahren bekannt und man weiss auch nicht, ob
eines existiert.
Schliesslich gibt es Funktionen von denen man weiss, dass sie nicht
berechenbar sind. Hierzu gehoeren die folgenden:
f(p) = 0, falls p ein terminierendes Javaprogramm ist, 1 sonst.
f(p) = 0, falls das Gleichungssystem (mit +,*,Variablen, Konstanten) p
eine Loesung in ganzen Zahlen hat, 1 sonst.
f(G,w) = 1, falls G eine Typ-0 Grammatik ist und w:L(G); 0 sonst.
f(p) = 0, falls der Satz von Kacheln p (Quadrate mit gefaerbten Kanten)
es erlaubt, die Ebene zu pflastern (nur gleichfarbige Kanten duerfen
aneinanderstossen); 1 sonst.
f(G1,G2) = 1, falls G1 und G2 Typ-2 Grammatiken sind und L(G1)
geschnitten mit L(G2) nicht leer ist. 0 sonst.
Mehrstellige Funktionen kann man durch Erweiterung des Alphabets um
Klammersymbole und Kommas leicht auf einstellige zurueckfuehren, daher
beschraenken wir uns im folgenden auf einstellige Funktionen.
Definition: eine partielle Funktion f:Sigma* -> Sigma* ist Turing
berechenbar, wenn eine deterministische Turingmaschine M existiert,
sodass
f(w) = v impliziert z0 w |-* []..[] z v [] .. []
wobei z:E und
f(w) undefiniert und z0 w |-* alpha z beta impliziert z nicht in E.
Church'sche These: Die intuitiv berechenbaren Funktionen stimmen mit
den Turing berechenbaren ueberein.
"Beweis": "<=" die Berechnung auf einer deterministischen
Turingmaschine entspricht der Vorstellung eines intuitiven
Berechnuncgsverfahrens.
"=>": ist ein Rechenverfahren in einem vernuenftigen
Detaillierungsgrad gegeben, so kann man es auch auf einer
Turingmaschine "ausprogrammieren". Wichtig hierbei ist, dass sich
mehrere Zwischenergebnisse auf dem einen Band durch
Hintereinanderschreiben unter Zuhilfenahme von Separatorsymbolen
abspeichern lassen. Schreib-Lese-Zugriff auf diese sequentiell
gespeicherten Daten ist umstaendlich aber nicht unmoeglich.
2. Berechnungsmodelle
=====================
Zur Untermauerung der Church'schen These werden wir nun verschiedene
Berechnungsmodelle studieren und deren Aequivalenz nachweisen.
2.1 Mehrband Turingmaschinen.
-----------------------------
Man kann eine Turingmaschine auch mit mehreren Baendern und
enstprechend mehreren unabhaengig bewegbaren Schreib-Lese-Koepfen
ausstatten. In diesem Fall verwendet man eine Uebergangsfunktion des
folgenden Typs (n die Zahl der Baender), wobei wir der Einfachheit
halber nur die deterministische Variante angeben:
delta : Z * Gamma^n -> Z * Gamma^n * {L,R,N}^n
Ist also delta(z,g1..gn) = (z',(g1'..gn'),(d1..dn')), so bedeutet das,
dass die Maschine im Zustand z und bei den gelesen Symbolen g1..gn,
also g1 unter dem ersten Schreib-Lese-Kopf, g2 unter dem zweiten, etc,
in den Zustand z' uebergeht, die Symbole g1..gn durch g1'..gn' ersetzt
und die n Schreiblesekoepfe unabhaengig voneinander in die Richtungen
d1..dn bewegt. Ist also etwa d1=L und d2=R, so muss der erste Kopf
nach links und der zweite Kopf nach rechts bewegt werden.
Eine n-Band Turingmaschine berechnet eine partielle Funktion f :
Sigma*->Sigma* (Sigma das Eingabealphabet der Turingmaschine) wenn die
Maschine gestartet im Anfangszustand, erstes Band beschriftet mit
Eingabe w, erster Schreiblesekopf auf dem ersten Symbol von w, alle
anderen Baender leer, anhaelt genau dann wenn f(w) definiert ist und
dann das Ergebnis v=f(w) auf dem ersten Band links vom ersten
Schreiblesekopf steht.
Es ist klar, dass eine n-Band Maschine eine normale (also Einband)
Turingmaschine simulieren kann, indem nur das erste Band genutzt
wird. Die Umkehrung gilt allerdings auch in folgendem Sinne:
Satz 25: Sei M eine n-Band Turingmaschine und f:Sigma*->Sigma*
eine partielle Funktion derart dass M f berechnet. Dann existiert auch
eine 1-Band Turingmaschine, die f berechnet.
Beweis: Wir verwenden das neue Alphabet Gamma' = (Gamma *
{_,*})^n. Ein Band, dessen Felder mit diesem Alphabet beschriftet
sind, laesst sich auffassen als ein Band mit 2n Spuren, wobei die
Spuren mit gerader Nummer mit Symbolen aus Gamma beschriftet sind und
die Spuren ungerader Nummer mit Symbolen aus {_,*}. Solch ein Band
wiederum ist in 1-1 Beziehung mit n Baendern und den zugehoerigen
Kopfpositionen. Man legt die n Baender einfach irgendwie uebereinander
und markiert die jeweilige Kopfposition mit einem * in der unmittelbar
darunterliegenden Spur. Es verbleibt nun die Aufgabe, die Bewegungen
und Aktionen der n Band Maschine auf der Ebene dieser Kodierung durch
die 1 Band Maschine nachzuvollziehen. Hierzu gehen wir davon aus, dass
sich der Schreiblesekopf links von allen * Markierungen befindet. Um
nun eine einzige Aktion der n Band Maschine zu simulieren, wird der
Kopf solange nach rechts bewegt, bis er an allen * Markierungen
vorbeigefahren ist. Deren Zahl n ist fest und kann daher im endlichen
Zustand der 1 Band Maschine gemerkt werden. Hierbei merkt sich die
Maschine auch alle n Gamma-Symbole, die an den jeweiligen
Kopfpositionen stehen. Nunmehr kann die 1-Band Maschine die
entsprechende Aktion der n-Band-Maschine auswaehlen und beim
Zurueckgehen durchfuehren. QED
2.2 LOOP Programme
------------------
Die Syntax der LOOP Programme ist wie folgt erklaert:
P ::= x_i := x_j + 1 /* Wertzuweisung, i,j:N */
| x_i := x_j - 1 /* Wertzuweisung, i,j:N */
| x_i := 0 /* Wertzuweisung, i:N */
| LOOP x_i DO P END /* x_i fache Ausfuehrung von P */
| P ; P /* Hintereinanderausfuehrung */
Zum Beispiel ist
x_0 := 0
LOOP x_1 DO
x_0 := x_0 + 1;
x_0 := x_0 + 1;
END
ein LOOP Programm. Nach seiner Abarbeitung hat x_2 den doppelten Wert
von x_1.
2.2.1 Semantik:
Formal ist die Semantik eines LOOP Programms eine partielle Funktion, die
Belegungen der Variablen auf Belegungen der Variablen abbildet. Solch
eine Belegung ordnet den Variablen Werte in N zu, wobei alle bis auf
endlich viele Variablen den Wert 0 bekommen.
Ist eta solch eine Belegung, so bezeichnen wir mit [[P]]eta die
Belegung nach Ausfuehrung von P. Es gilt:
1) [[x_i:=x_i+1]]eta = eta[xi |-> eta(xi)+1]
2) [[x_i:=x_i-1]]eta = eta[xi |-> eta(xi) -. 1], wobei x-.y = x-y, falls
x>=y und 0 sonst.
3) [[x_i := 0]]eta = eta[x_i |-> 0]
4) [[LOOP x_i DO P END]]eta = f^n(eta), wobei f(eta) = [[P]](eta) und
n = eta(x_i).
5) [[P1;P2]]eta = [[P2]]([[P1]]eta)
2.2.2 Abgeleitete Konstrukte
Wir fuehren die folgenden Abkuerzungen als "syntaktischen Zuckerguss"
ein:
x_i := x_j + c, wobei c:N, c>0 ist eine Abkuerzung fuer
x_i := x_j + 1; x_i := x_i + 1; .... ; x_i := x_j + 1;
/* c
Zuweisungen, die erste mit x_j, die anderen mit x_i */
Ebenso lassen sich die Anweisungen
x_i := x_i - c,
x_i := c
definieren.
SIGN x_i ist eine Abkuerzung fuer
LOOP x_i DO x_i:=1 END
Hat x_i den Wert 0, so hat x_i auch nach SIGN x_i den Wert 0. Hat x_i
einen Wert >0, so hat x_i nach Ausfuehrung von SIGN x_i den Wert 1.
IF x_i THEN P END ist eine Abkuerzung fuer
x_j:=x_i;
SIGN x_j;
LOOP x_j DO
P;
END;
wobei j groesser als alle im Gesamtprogramm vorkommenden
Variablennummern ist. Wir sagen, x_j sei eine frische Variable.
IF x_i THEN P ELSE Q END ist eine Abkuerzung fuer
x_j := 1
IF x_i THEN P;x_j := 0 END;
IF x_j THEN Q END
auch hier ist x_j eine frische Variable.
2.2.3 LOOP Berechenbarkeit
Definition: Sei f:N^n -> N eine Funktion. Das LOOP Programm P
berechnet die Funktion f, wenn nach Inititalisierung der Variablen
x_1,...,x_n mit Argumenten v_1,...,v_n und Initialisierung aller
anderen Variablen mit 0 die Abarbeitung von P zu einer Belegung
fuehrt, in der x_0 den Wert f(v_1,...,v_n) hat. Eine Funktion, die von
einem LOOP Programm berechnet wird, heisst LOOP-berechenbar.
Beispiel:
Sei P =
x_3 := x_1 + c;
LOOP x_1 DO
x_1 := x_1 - c;
IF x_1 THEN
x_2 := x_2 + 1;
x_3 := x_3 - c;
END;
END;
Das Programm P;x_0:=x_2 berechnet die Funktion x DIV c; das Programm P;x_0:=x_3
berechnet die Funktion x MOD c, jeweils fuer festes c.
Das Programm
LOOP x_2 DO x_1 := x_2 + 1 END;x_0 := x_1
berechnet die Funktion x+y.
Ebenso berechnet man auch die Differenz zweier Zahlen.
Ist f bereits als LOOP-berechenbar identifiziert, so fuehren wir die
Abkuerzung
x_i := f(x_i1,...,x_in)
ein, welche den Effekt hat, der Variablen x_i den Funktionswert der
Werte der x_ij zuzuweisen. Um diese Abkuerzung tatsaechlich zu
implementieren, muss man etwas buchhalterisch vorgehen und zwar
besteht das Programmstueck x_i := f(x_i1,...,x_in) aus der
Hintereinanderausfuehrung dreier Programme, P1;Pf;P2, wobei Pf ein
LOOP Programm ist, welches f berechnet. Das Programm P1 kopiert den
Inhalt aller Variablen, die von Pf benutzt werden in frische Variablen
und initialisiert die von f benutzten Variablen auf 0, bzw auf die
verlangten Argumentwerte. Das Programm P2 restauriert die von Pf
verwendeten Variablen zu ihren alten Werten und schreibt ausserdem x_0
nach x_i.
Mit dieser Abkuerzung koennen wir nun auch die Division als
zweistellige Funktion implementieren unter Verwendung von
x_4 := x_1 + x_2;
LOOP x_1 DO
x_1 := x_1 - x_2;
IF x_1 THEN
x_3 := x_3 + 1;
x_4 := x_4 - c;
END;
END;
Weitere LOOP-berechenbare Funktionen sind Multiplikation,
Exponentiation, Fakultaet, aber auch eher symbolische Funktionen, wie
etwa f(x,y) = 1, falls die Binaerdarstellung von y in der von x
vorkommt.
2.3 WHILE Programme
Die WHILE Programme bilden eine Erweiterung der LOOP um eine
While-Schleife, bei der solange iteriert wird, bis eine bestimmte
Bedingung eintrifft.
Formal geschieht dies durch Hinzufuegen der folgenden Klausel zur BNF Grammatik
P ::=
| WHILE x_i DO P END /* Wiederholte Ausfuehrung von P bis x_i = 0*/
Die Semantik einer solchen While Schleife ist, dass der Rumpf solange
ausgefuehrt wird, bis der Wert von x_i Null ist. Die Semantik ist
undefiniert, falls dieses Ereignis nie eintritt.
4) [[WHILE x_i DO P END]]eta = f^n(eta), wobei f(eta) = [[P]](eta) und
n die kleinste natuerliche Zahl ist, sodass [[P]](eta)(x_i) = 0.
Natuerlich kann man die LOOP Schleife durch die WHILE Schleife
codieren, sodass man dieses Konstrukt bei WHILE Programmen gar nicht
braeuchte.
Im Gegensatz zu LOOP Programmen koennen WHILE Programme auch ad
infinitum rechnen, also nicht terminieren, Beispiel: x_1:= 1; WHILE
x_1 DO x_1 := x_1 END. Daher erweitert man den Begriff der
Berechenbarkeit hier wie bei Turingmaschinen auf partielle
Funktionen.
Definition: Sei f:N^n -> N eine partielle Funktion. Das WHILE Programm P
berechnet die Funktion f, wenn nach Inititalisierung der Variablen
x_1,...,x_n mit Argumenten v_1,...,v_n und Initialisierung aller
anderen Variablen mit 0 die Abarbeitung von P genau dann terminiert,
wenn f(v1,...,vn) definiert ist und in diesem Falle zu einer Belegung
fuehrt, in der x_0 den Wert f(v_1,...,v_n) hat. Eine Funktion, die von
einem WHILE Programm berechnet wird, heisst WHILE-berechenbar.
Natuerlich sind echt partielle Funktionen hoechstens WHILE, aber nicht
LOOP berechenbar; es gibt aber auch totale Funktionen, die nur WHILE,
aber nicht LOOP berechenbar sind. Ein konkretes Beispiel gibt es
spaeter.
2.3.1 Simulation von WHILE-Programmen durch Turingmaschinen.
Satz 26: Jede WHILE-berechenbare Funktion ist auch Turing berechenbar.
Beweis: Wir ordnen jeder Zahl k und jedem WHILE Programm, das
hoechstens die Variablen x_0,...,x_k verwendet,
eine Turingmaschine mit >= k+1 Baendern zu. Der Inhalt
des Bandes i, wobei i=0,...,k soll den Inhalt der Variablen x_i in Binaerdarstellung
repraesentieren. Die anderen moeglicherweise verwendeten Baender sind
Arbeitsbaender, die zum Beispiel dazu dienen, Variablen
zwischenzuspeichern, wie das ja schon bei der Einfuehrung der
Kurznotation x_i := f(xs) gemacht wurde.
Die Turingmaschine wird durch Induktion ueber den Aufbau des WHILE
Programms konstruiert.
Fall 1: x_i := x_j + 1. Wir kopieren xj auf ein Hilfsband, simulieren
auf diesem die schon bekannte
Addiermaschine und kopieren dann das Hilfsband nach x_i.
Fall 2: x_i := x_j - 1. Hier benoetigen wir eine
Subtrahiermaschine. Sie ist analog zur Addiermaschine.
Fall 3: x_i := 0. Das ist klar.
Fall 4: P1;P2. Seien M1 und M2 die Maschinen, die P1 und P2
simulieren. Die zu konstruierende Maschine M fuer P1;P2 wird sich
zunaechst wie M1 verhalten, sodann aber alle Hilfsbaender loeschen und
M2 starten.
Fall 4: WHILE x_i DO P END. Sei M die Maschine, die P simuliert.
Die gesuchte Maschine geht aus M dadurch hervor, dass
Anfangszustand und Endzustaende zu "ganz normalen" Zustaenden
werden, die dazu verwendet werden, die Maschine M solange immer
wieder zu starten, bis das Band i den Inhalt Null aufweist. Vor
jedem Neustart von P muessen die von M eventuell verwendeten
Hilfsbaender wie bei der sequentiellen Komposition auf Null gesetzt werden.
QED
2.4 GOTO Programme
------------------
Fuer die umgekehrte Richtung also die Simulation von Turingmaschinen
durch WHILE Programme sind die assemblernahen GOTO Programme
nuetzlich. Diese Programme (P) verwenden neben den Variablen x_0, x_1,
... noch Marken M_0, M_1, ... welche Anweisungen (A) markieren und als
Sprungadressen dienen.
Ein GOTO - Programm besteht aus einer durch Semikolon getrennten Folge
von markierten Anweisungen der Form M_i : A. Die Anweisungen sind
*) x_i := x_j +/- 1 /* Wertzuweisung */
*) GOTO M_i /* unbedingter Sprung */
*) IF x_i THEN GOTO M_j /* bedingter Sprung */
*) HALT /* Erfolgreiche Beendigung des Programms */
Jede Marke darf nur einmal als Markierung einer Anweisung vorkommen. Hier ist ein
GOTO-Programm zur Berechnung der Addition:
M_1 : IF x_2 THEN GOTO M_3
M_2 : GOTO M_6
M_3 : x_1 := x_1 + 1
M_4 : x_2 := x_2 - 1
M_5 : GOTO M_1
M_6 : x_0 := x_1
M_7 : HALT
Die Semantik von GOTO-Programmen sollte intuitiv klar sein, man kann
sie formal entweder wie bei Turingmaschinen ueber eine
Ein-Schritt-Relation auf globalen Konfigurationen erklaeren
(operationale Semantik) oder ueber ein System rekursiv definierter
Funktionen (denotationelle Semantik), s. Uebung.
Berechnung von Funktionen durch GOTO-Programme und
GOTO-Berechenbarkeit werden genauso wie bei WHILE Programmen
definiert:
Marken, die nicht angesprungen werden, lassen wir weg, ausserdem
erlauben wir uns auch noch ein IF-THEN-ELSE mit zwei Sprungmarken,
welches leicht ausgedrueckt werden kann. Verwenden wir dann noch
symbolische Sprungadressen, dann sehen die GOTO Programme gar nicht
mehr so schlimm aus:
"add(x_1,x_2)" : IF x_2 THEN GOTO "add(x_1,x_2),x_2=/=0" ELSE GOTO "return x_1"
"add(x_1,x_2),x_2=/=0" :
x_1 := x_1 + 1;
x_2 := x_2 - 1;
GOTO "add(x_1,x_2)"
"return x_1" :
x_0 := x_1;
HALT
Hier sieht man, dass ein GOTO-Programm eigentlich nichts anderes ist,
als ein System endrekursiver Funktionen. Ich meine, dass das Konzept
etwas zu unrecht durch einflussreiche Arbeiten von Dijkstra und Hoare
"GOTO considered harmful", "strukturierte Programmierung", zugunsten
von while-Schleifen verdraengt wurde.
Wie dem auch sei, WHILE und GOTO Programme sind aequivalent; wie man
eine WHILE-Schleife durch GOTO's ausdrueckt sollte klar sein:
WHILE x_i DO P entspricht
"loop" : IF x_i THEN GOTO "body" ELSE GOTO "done"
"body" : P; GOTO "loop"
"done" : rest des Programms
Etwas interessanter ist die Umkehrung:
Satz 27: Jede GOTO-berechenbare Funktion ist auch WHILE berechenbar.
Beweis: Sei P ein GOTO-Programm mit den Marken M0,...,Mn. Wir
repraesentieren die aktuell zu bearbeitende Marke (Programmzaehler)
durch eine frische Variable pc, also pc = x_j fuer j gross genug. Die
Variablen von P werden durch dieselben Variablen des zu
konstruierenden WHILE-Programms repraesentiert. Ohne Beschraenkung der
Allgemeinheit nehmen wir an, dass P die Form
M_0 : A_0; M_1 : A_1; ... ; M_n : HALT
hat und dass keine der A_1,..A_n-1 die HALT Anweisung ist.
Nunmehr konstruieren wir unser WHILE Programm wie folgt:
pc := 1;
WHILE pc =/= n DO
IF pc = 1 THEN /* Simuliere A_1 */
IF pc = 2 THEN /* Simuliere A_2 */
...
IF pc = n-1 THEN /* Simuliere A_n-1 */
END
Das "Simulieren" einer Wertzuweisung x_i:=x_j+1 erfolgt durch x_i:=x_j+1;pc:=pc+1
Das "Simulieren" der anderen Zuweisungen erfolgt analog
Das "Simulieren" einer Sprunganweisung GOTO M_j erfolgt durch pc:=j
Das "Simulieren" eines bedingten Sprungs IF x_i THEN GOTO M_j erfolgt
durch IF x_i THEN pc:=j ELSE pc:=pc+1
Die HALT Anweisung wird nicht simuliert, da keine der A_1,...A_n-1
eine solche ist.
Es ist klar, dass das resultierende Programm dieselbe Funktion wie P
berechnet. QED
Durch Hin- und Zurueckuebersetzen sieht man hieraus, dass man jedes
WHILE Programm in eine Form bringen kann, in der nur eine einzige
WHILE-Schleife benutzt wird. Dies ist die Kleene Normalform. Intuitiv
"WHILE noch nicht fertig DO einen Schritt weiterrechnen END".
Wir bemerken, dass eine solche Normalform bei LOOP Programmen nicht
verfuegbar ist, so erfordert zum Beispiel die Multiplikation auf jeden
Fall zwei geschachtelte LOOP Schleifen.
Satz 28 Jede Turing-berechenbare Funktion ist auch GOTO berechenbar.
Beweis: Sei M eine (deterministische) 1-Band Maschine, die eine Funktion f berechnet. Sei
weiter c=|Gamma| die Groesse des Alphabets. O.B.d.A sei
Gamma={0,1,2,3,...,c-1} und Z={0,1,...,q-1}.
Wir repraesentieren eine Konfiguration alpha z beta durch drei
Variablen x_alpha, x_beta, x_z. Hierbei enthaelt x_alpha das Wort
rev(alpha), also alpha von rechts nach links gelesen,
aufgefasst als Zahl im c-er System. Weiter enthaelt x_beta das
Wort beta, also von links nach rechts gelesen,
aufgefasst als Zahl im c-er System. x_z
schliesslich enthaelt den Zustand. Formal gilt, falls alpha =
a(m-1)..a(0), beta=b(0)..b(n-1), dann
x_alpha = sum(i=0..m-1,c^i a(m-1-i))
x_beta=sum(j=0..n-1,c^ib(i))
Das Symbol an der Kopfposition ergibt sich also zu x_beta MOD c; das
Symbol links neben der Kopfposition ergibt sich also zu x_alpha MOD c;
das Symbol rechts neben der Kopfposition ergibt sich also zu
x_beta DIV c MOD c.
Jetzt fuehren wir fuer jeden Zustand z eine Marke M_z ein. An jeder
Marke steht nun eine Folge von Anweisungen, die wir aus der
Uebergangsfunktion delta ablesen. Die Reihenfolge der Anweisungen ist
beliebig.
Falls delta(z,a) = (z',b,L) so schreibe an die Marke M_z die Anweisung
IF beta MOD c = a THEN
x_beta := ((x_beta DIV c) * c + b) * c + x_alpha MOD c;
x_alpha := x_alpha DIV c;
GOTO M_z'
Falls delta(z,a) = (z',b,R)
IF beta MOD c = a THEN
x_alpha := x_alpha * c + b;
x_beta := x_beta DIV c;
GOTO M_z'
Falls delta(z,a) = (z',b,N)
IF beta MOD c = a THEN
x_beta := (x_beta DIV c) * c + b;
GOTO M_z'
Falls z ein Endzustand ist, so schreibe an M_z die Anweisung HALT und
sonst nichts. (Eine Turingmaschine sollte keine Uebergaenge aus
Endzustaenden haben, da sie (im Gegensatz zu endlichen Automaten und
DPDA!) bei Erreichen eines Endzustandes sofort stehenbleibt.
Hier haben wir IF-THEN etwas freier als eigentlich erlaubt
verwendet. Die Uebersetzung in die formale Syntax sollte klar sein.
Wir beginnen nun die Programmausfuehrung bei M_z0, ggf indem wir als
erste Anweisung dorthin springen. Es sollte klar sein, dass auf diese
Weise M korrekt simuliert wird. QED.
Wir haben jetzt gesehen, dass die folgenden Formalismen allesamt
aequivalent sind, was deren Berechnungskraft betrifft:
1-Band TM
Mehrband TM
WHILE Programme
GOTO Programme
2.5 Primitive Rekursion
-----------------------
Wir lernen nun ein eher mathematisch motiviertes Berechnungsmodell
kennen, welches den LOOP Programmen entspricht.
Definition: Die Klasse der primitiv rekursiven Funktionen ist die
kleinste Klasse von (ein oder mehrstelligen) Funktionen auf den
natuerlichen Zahlen, die den folgenden Bedingungen genuegt:
1) Die im folgenden genannten Grundfunktionen sind primitiv rekursiv.
*) Nachfolgerfunktion succ(x)=x+1
*) Projektionen proj_(n,i)(x_1,..,x_n) = x_i
*) Konstante Null 0(x)=0
2) Komposition: Sind f(x1..xn) und g1(ys),..., gn(ys) primitiv rekursiv, so auch
h(ys) = f(g1(ys),...,gn(ys)) (Komposition). Man beachte, dass ys
fuer einen Variablenvektor y1..ym steht.
3) Primitive Rekursion: Erfuellt f ein Gleichungssystem der Form
f(0,ys) = g(ys)
f(x+1,ys) = h(x,f(x,ys),ys)
mit primitiv rekursiven Funktionen g, h, so ist auch f primitiv
rekursiv.
Will man zeigen, dass eine Funktion primitiv rekursiv ist, so muss man sie
also, falls es sich nicht gerade um eine Grundfunktion handeln sollte,
aus schon als primitiv rekursiv erkannten Funktionen durch Komposition
oder primitive Rekursion definieren.
Zum Beispiel ist die Funktion add(x,y)=x+y primitiv rekursiv, denn sie
entsteht durch Komposition aus der Funktion add'(x,y)=y+x, naemlich
add(x,y) = add'(proj_(2,2)(x,y), proj_(2,1)(x,y))
und add' erfuellt das Gleichungssystem
add'(0,x) = x = proj_(1,1)(x)
add'(y+1,x) = h(y, add'(y,x), x)
wobei h(y,z,x) = succ(z) = succ(proj_(3,2)(x,y,z))
Natuerlich haette man die Addition auch durch Rekursion ueber das
erste Argument definieren koennen und sich dadurch ein paar
Zwischenschritte erspart.
In der Praxis laesst man auch etwas verallgemeinerte
Rekursionsschemata zu, wie zum Beispiel
add(x,0) = x
add(x,y+1) = succ(add(x,y))
wobei es sich versteht, dass ein solches Schema durch Einsetzen von
Projektionen und Kompositionen in eine "offizielle" Definition
verwandelt werden kann.
Ein weiteres Beispiel ist die Vorgaengerfunktion u(x) = max(x-1,0) (modifizierte
Differenz)
Hier hat man
u(0) = 0
u(x+1) = x
also formal
u(0) = 0
u(x+1) = proj_(2,1)(x,u(x))
Durch weitere primitive Rekursion laesst sich daraus die allgemeine
Subtraktion definieren.
Satz 29. Die folgende Funktion ist eine primitiv rekursive Bijektion
von N x N nach N.
/ x+y+1 \
c(x,y) = (x+y+1)(x+y) / 2 + x = | | + x (Binomialkoeffizient)
\ 2 /
Ausserdem sind die durch e(c(x,y)) = x, f(c(x,y))=y
definierten Inversen von c primitiv rekursiv.
Beweis. Wir setzen b(n) = n(n-1)/2 (Binomialkoeffizient) und
beobachten b(0)=0, b(n+1)=b(n)+n, somit ist b primitiv rekursiv. Es
gilt aber c(x,y)=b(x+y+1)+x, somit ist auch c als primitiv rekursiv
erwiesen.
Zum Beweis der Surjektivitaet argumentieren wir wie folgt:
0=c(0,0). Ist z=c(x,y), mit y>0, so ist z+1=c(x+1,y-1). Ist dagegen
z=c(x,0), so ist z+1=c(0,x+1). (Es gilt naemlich c(0,x+1) =
choose(x+2,2) = choose(x+1,2)+x+1 = c(x,0)+1).
Der Beweis der Injektivitaet erfolgt durch Induktion ueber
z=c(x,y). Ist c(x,y)=0, so folgt x=y=0. Ist c(x,y)=c(x',y')=z+1, dann
sind drei Faelle zu unterscheiden:
x>0, x'>0: es folgt c(x-1,y+1)=c(x-1,y'+1)=z. Die Behauptung folgt mit
der Induktionshypothese.
x=0, x'=0: es folgt c(y-1,0)=c(y'-1,0)=z. Induktionshypothese.
x=0, x'>0: es folgt c(y-1,0)=c(x'-1,y'+1)=z, also nach IH
y'+1=0, was ein Widerspruch ist.
Da man nun weiss, dass c bijektiv ist, kann man die Inversen durch
systematische Suche ausrechnen:
e(z) = max({x <= z | es existiert y <= z. c(x,y)=z} u {0})
Um dies als primitiv rekursiv zu erweisen, definieren wir zunaechst
eine Hilfsfunktion
P(x,z,k) = 1, falls es existiert y<=k sodass c(x,y)=z, 0 sonst.
Es gilt P(x,z,0) = eq(c(x,0),z) wobei eq(u,v)=sign(u-v)+sign(v-u) und
sign(0)=0, sign(x+1)=1 (letzteres ist eine primitive Rekursion!)
Ausserdem gilt P(x,z,k+1) = max(P(x,z,k), eq(c(x,k+1),z))
wobei max(x,y) = (x-y)+y.
Somit ist P primitiv rekursiv.
Des weiteren definieren wir eine Hilfsfunktion
Q(z,k) = max({x <= z | P(x,z,z)=1} u {0})
Es gilt
Q(z,0) = 0,
Q(z,k+1) = max((k+1)*P(k+1,z,z), Q(z,k))
Schliesslich hat man
e(z) = Q(z,z). Die Definition von f erfolgt analog. QED
Satz 30: Jede primitiv rekursive Funktion ist LOOP berechenbar.
Beweis: Die Grundfunktionen sind sicherlich LOOP-berechenbar und
ausserdem sind die LOOP-berechenbaren Funktionen unter Komposition
abgeschlossen. Es bleibt zu zeigen, dass eine aus LOOP-berechenbaren
Funktionen durch primitive Rekursion definierte Funktion
auch LOOP-berechenbar ist. Sei also
f(0,y) = g(y)
f(x+1,y) = h(x,f(x,y),y)
Der Einfachheit halber erlauben wir nur einen Parameter y. Der
allgemeine Fall ist aehnlich.
Das folgende LOOP Programm berechnet dann f:
x_0 := g(x_2);
x_3 := 0;
LOOP x_1 DO
x_0 := h(x_3,x_0,x_2);
x_3 := x_3+1
END
QED
Satz 31: Jede LOOP-berechenbare Funktion ist primitiv rekursiv.
Beweis: Wir verwenden folgende Bijektion von N* auf N:
code([x0,...,x_n]) = c(x_0,c(x_1,...,c(x_n,0)...))
Sie hat die Inversen d_0(z) = e(z), d_1(z) = e(f(z)), d_2(z) =
e(f(f(z))), etc pp.
Wir definieren ausserdem die Funktion set_i(x,z) durch
set_i(x,z) =
c(d_0(z),c(d_1(z),...,c(d_(i-1)(z),x,f^(i+1)(z)...)
Es gilt set_i(x, code([x0,...,xn])) =
code([x0,...,x(i-1),x,x(i+1),...,xn]).
Wir koennen jetzt auch Variablenbelegungen durch einzelne
Zahlen codieren:
code(eta) = code([eta(x_0), eta(x_1), ... , eta(x_n)]), wobei
n so gross gewaehlt ist, dass eta(x_m)=0 fuer m>n.
Man beachte, dass fuer alle i gilt d_i(code(eta)) = eta(x_i).
Durch Induktion ueber den Aufbau von LOOP Programmen ordnen
wir jetzt jedem LOOP Programm P eine primitiv rekursive
Funktion f_P zu, derart dass f_P(code(eta)) =
code([[P]](eta)).
Ist P = x_j := x_i+1, so ist f_P(z) = set_j(d_i(z)+1,z).
Die anderen elementaren Anweisungen sind analog.
Ist P = P1;P2, so ist f_P(z) = f_P2(f_P1(z))
Ist P = LOOP x_i DO P1 END, so ist f_P(z) = t(d_i(z),z) wobei
t(0,z) = z
t(k+1,z) = f_P1(t(k,z))
Ist nun f(x1,...,xn) LOOP berechenbar durch das LOOP Programm
P, so ist f auch primitiv rekursiv, da ja
f(x1,...,xn) = d_0(f_P(c(0,c(x1,c(x2,...,c(xn,0))))))
QED
2.6. mu-Rekursion
-----------------
Um auch die WHILE Programme durch Rekursionsmuster in den
Griff zu bekommen, fuehren wir noch die sogenannte mu-Rekursion
ein:
Definition: Sei g(n,x1,...,xk) eine k+1 stellige partielle
Funktion auf N. Die k-stellige partielle Funktion f(x1,...,xk)
entsteht aus g durch mu-Rekursion, wenn gilt
/ das kleinste n, sodass g(n,xs)=0
| und g(k,xs) fuer k<=n definiert ist.
f(x1,...,xk) = <
|
\ undefiniert, falls kein solches n existiert.
Man schreibt: f(xs) = mu n.g(n,xs).
Erinnerung: x-vektor wird als xs geschrieben.
Man beachte, dass f das folgende (endrekursive, aber nicht primitiv
rekursive) Rekursionsschema erfuellt:
f(xs) = h(0,xs)
h(n,xs) = n, falls g(n,xs)=0, h(n+1,xs) sonst.
Definition: Die mu-rekursiven Funktionen sind die kleinste Klasse von
Funktionen, die die primitiv rekursiven Grundfunktionen enthaelt und
unter Komposition, primitiver Rekursion und mu-Rekursion abgeschlossen
ist.
Mit der mu-Rekursion gelingt es nun, auch die WHILE-Schleife zu
simulieren und zwar in derselben Weise, wie wir auch schon die
LOOP-Programme simuliert haben:
Ist P = WHILE x_i DO P END, so setzen wir
f_P(z) = iter(num(z), z),
wobei iter(0,z) = z und iter(n+1,z) = f_P1(iter(n,z)), also iter(n,z)
= f_P1^n(z) und num(z) = mu n.d_i(iter(n,z))
Die Codierung ist ineffizient, da man die Anzahl der erforderlichen
Iteration separat von der eigentlichen Iteration ausrechnet. Das liegt
in der Natur der mu-Rekursion.
Auf der anderen Seite laesst sich die mu-Rekursion leicht durch eine
WHILE-Schleife implementieren, sodass wir zusammengefasst folgendes
gezeigt haben:
Satz 32: Die Klasse der mu-rekursiven Funktionen stimmt mit der Klasse
der WHILE-berechenbaren Funktion (und damit mit der Klasse der
Turing-berechenbaren) Funktionen ueberein.
Wir haben nunmehr die folgenden allesamt aequivalenten
Berechnungsbegriffe kennengelernt: Turingmaschinen (1Band, Mehrband),
WHILE-Programme, GOTO-Programme, mu-Rekursion. Auf der anderen Seite
wurde noch kein maechtigeres Berechnungsmodell gefunden, welches
gleichzeitig beanspruchen kann, den intuitiven Berechenbarkeitsbegriff
zu erfassen.
Maechtigere Modelle gibt es viele, erlaubt man etwa die Operation mu' definiert durch
mu' n.f(n,xs) = "das kleinste n sodass f(n,xs)=0; 0 falls kein solches n existiert"
so kann man zeigen, dass mehr Funktionen berechenbar werden;
andererseits ist mu' n.f(n,xs) im allgemeinen nicht intuitiv
berechenbar; wie soll man denn feststellen, ob keine solche Nullstelle
von f existiert?
Wir wollen jetzt noch zeigen, dass die LOOP-berechenbaren Funktionen und damit die
primitiv rekursiven Funktionen eine echte Teilmenge der berechenbaren Funktionen bilden.
2.7. Die Ackermannfunktion
--------------------------
Die Ackermannfunktion A : N x N -> N ist wie folgt rekursiv definiert:
A(0,y) = y+1
A(x+1,0) = A(x,1)
A(x+1,y+1) = A(x,A(x+1,y))
Es gilt also A(x,y) = B_x(y), wobei
B_0(y) = y+1
B_(x+1)(y) = B_x(B_x(...B_x((1)...) (y+1 malige Anwendung)
Hieraus folgt sofort, dass A(x,y) fuer alle x,y definiert ist und dass
B_x fuer festes x primitiv rekursiv ist. Wir werden jetzt zeigen, dass
A selbst nicht primitiv rekursiv ist. Auf der anderen Seite ist A
intuitiv berechenbar, da man ja die rekursive Definition als
Javaprogramm auffassen kann. Um weitere Evidenz fuer die Church'sche
These aufzubauen und als Beispiel dafuer, wie man allgemeine
Rekursionsschemata als WHILE Programme implementiert, wollen wir auch
noch formal die WHILE-berechenbarkeit der Ackermannfunktion
nachweisen.
Satz 33: Die Ackermannfunktion ist WHILE-berechenbar.
Beweis: Wir definieren zunaechst wie folgt eine Verallgemeinerung der
Ackermannfunktion auf Listen: Die Funktion
AList : N* * N -> N
ist definiert durch:
AList([x1,...,xn],y) = A(xn,A(x(n-1),...A(x3,A(x2,A(x1,y)))...)
Es gilt nun (in funktionalem Pseudocode):
AList([],y) = y
AList(0 :: l, y) = AList(l,y+1)
AList(x+1 :: l, 0) = AList(x::l, 1)
AList(x+1 :: l, y+1) = AList(x+1 :: x :: l, y)
A(x,y) = AList([x],y)
Diese Definition ist aber endrekursiv und kann somit direkt in eine
WHILE Schleife uebersetzt werden. Um ein WHILE-Programm zu erhalten,
muessen wir noch die Liste als natuerliche Zahl repraesentieren, was
wiederum durch die Paarungsfunktion c(-,-) (mit den Inversen e und f) gelingt:
/* Das folgende WHILE Programm berechnet die Ackermannfunktion */
l:=c(x_1,0);
y:=x_2;
WHILE l DO
x := e(l);
IF x = 0
THEN l := f(l);y:=y+1
ELSE IF y = 0
THEN l:=c(x-1,f(l)); y:=1
ELSE l:=c(x,c(x-1,f(l))); y:=y-1
END
END
END
x_0 := y
QED
Satz 34: Die Ackermannfunktion ist nicht LOOP-berechenbar und damit
nicht primitiv rekursiv.
Beweis: Man zeigt zunaechst die folgenden arithmetischen
Eigenschaften der Ackermannfunktion.
i) A(x,y) ist streng monoton wachsend in x und y.
ii) Fuer alle c1, c2 existiert c3, sodass
A(c2, A(c1, y)) <= A(c3, y)
iii) Fuer alle c1 existiert c2, sodass
B_c1^x(x) <= A(c2,x)
i) ist Lemma B und D in Schoenings Buch. Man beweist es durch
Induktion
ii) Folgt aus der Monotonie und der Definition, siehe auch
Schoening. Man kann setzen c3 := max(c1-1,c2)+2.
iii) B_c1^x(x) <= B_c1^x(B_c1^x(1)) <= B_c1^(2x)(1) <= B_c2^x(1) =
A(c2+1,x) wobei c2 aus ii) erhalten wird.
Fuer Variablenbelegung eta schreiben wir max(eta) fuer max(eta(x_i) |
i>=0). Da nur endlich viele eta(x_i) von Null verschieden sind, ist
i>das wohldefiniert.
Fuer LOOP-Programm P definieren wir die Funktion f_P durch
f_P(x) = max{ max([[P]](eta)) | max(eta)<=x}
Also ist f_P(x) der groesstmoegliche Variableninhalt, der nach
Ausfuehrung von P erreichbar ist, falls alle Variablen mit Werten <= x
vorbesetzt werden.
Durch Induktion ueber den Aufbau der LOOP Programme zeigen wir nun
folgendes:
Lemma: Fuer jedes LOOP Programm P existiert eine Konstante c, sodass
f_P(x) <= B_c(x) = A(c,x)
Beweis des Lemmas:
Ist P eine Wertzuweisung, so kann man c=0 waehlen, denn es ist f_P(x)
<= x+1 = A(0,x).
Ist P=P1;P2 und sei f_P1(x) <= B_c1(x), f_P2(x) <= B_c2(x). Es gilt
f_P(x) = max{max(P2(P1(eta))) | max(eta)<=x} <=
max{max(P2(rho)) | max rho <= f_P1(x)} = f_P2(f_P1(x)).
Also ist f_P(x) <= B_c2(B_c1(x)) <= B_c3(x) wg Eigenschaft ii)
Ist P=LOOP x_i DO P1 END und f_P1(x) < B_c1(x), so haben wir
f_P(x) <= f_P1(f_P1(...f_P1(x))...) <= B_c1^x(x) <= B_c2(x) mit
Eigenschaft iii)
\______ _______/
\/
<= x viele
Damit ist das Lemma bewiesen.
Der Beweis, dass die Ackermannfunktion nicht LOOP berechenbar ist, ist
jetzt ganz leicht: Waere die Ackermannfunktion LOOP-berechenbar, dann
auch die Funktion a(x) = A(x,x)+1. Dann aber gaebe es ein festes c,
sodass
a(x) = A(x,x)+1 <= A(c,x).
Das aber fuehrt zum Widerspruch, wenn man c = x einsetzt. QED
Ein anderes Beispiel fuer eine totale nicht LOOP-berechenbare Funktion
ist ein LOOP-evaluator:
eval(x,y) = f_P(y), falls x ein LOOP Programm P codiert, 0 sonst.
Waere naemlich eval(x,y) LOOP berechenbar, so auch
a(x) = eval(x,x)+1
Ist aber nun x0 Codierung eines (hypothetischen) LOOP-Programms P fuer
a(x), so haette man
eval(x0,x0) + 1 = a(x0) = f_P(x0) = eval(x0,x0).
Selbstverstaendlich ist aber eval eine berechenbare Funktion.
3: Unentscheidbarkeit, Halteproblem, Reduzierbarkeit
------------------------------------------------------
Definition: Eine Menge A <= N heisst entscheidbar, wenn ihre
charakteristische Funktion chi_A : N -> {0,1} wobei chi_A(x)=1
genau dann, wenn x:A ist, berechenbar ist.
Das bedeutet, dass es eine Turingmaschine gibt, die bei Eingabe x
immer haelt und genau dann 1 ausgibt, wenn x in A ist.
Definition: Eine Menge A <= N heisst semientscheidbar, wenn die
folgende partielle Funktion berechenbar ist:
1, falls x:A
chi'_A(x) = <
undefiniert sonst.
Das bedeutet, dass eine Turingmaschine gibt, die bei Eingabe x
anhaelt genau dann, wenn x:A ist und nicht terminiert, falls x nicht
in A ist.
Diese Begriffe verallgemeinern sich sofort auf Teilmengen von Sigma*
durch Fixierung einer geeigneten Codierung von Sigma* in N, etwa
mithilfe des |Sigma|-er Systems wie im Beweis, dass Turingmaschinen
durch WHILE-Programme simuliert werden koennen.
Natuerlich ist jede entscheidbare Menge auch semientscheidbar (bei
negativer Antwort schickt man die Maschine in eine
Endlosschleife). Die umgekehrte Richtung gilt allerdings nicht. Es
gibt Mengen, die semientscheidbar sind, aber nicht entscheidbar. Eine
solche wollen wir nunmehr kennenlernen:
Wir fixieren hierzu eine Codierung von Turingmaschinen als 0-1
Folgen durch Wahl irgendeines geeigneten Binaerformats.
Definition: Das Halteproblem H ist die folgende Teilmenge von N:
H = { c(x,y) | x codiert eine Turingmaschine M und M angewendet auf x
haelt}.
Das Halteproblem ist also intuitiv die Frage, ob eine gegebene
Turingmaschine auf gegebener Eingabe anhaelt. Diese Fragestellung ist
nicht entscheidbar (unentscheidbar):
Satz 35: Das Halteproblem ist unentscheidbar.
Waere das Halteproblem entscheidbar, dann waere auch die folgende
Funktion berechenbar:
/ 0, falls c(x,x) nicht in H (also, falls x angewendet auf x
| nicht haelt. )
|
f(x) = <
|
| undefiniert, falls c(x,x) in H (also falls x angewendet
\ auf x haelt.)
Man muss hierzu nur ein hypothetisches WHILE Programm (oder
Turingmaschine) fuer die charakteristische Funktion von H etwas
umbauen.
In diesem Fall gaebe es aber auch eine Turingmaschine M, die f berechnet
und diese Maschine M haette dann eine Codierung, sagen wir x0.
Nachdem M die Funktion f berechnet, gilt insbesondere
1) f(x0) ist definiert genau dann wenn M angewendet auf x0 haelt.
Aufgrund der Definition der Funktion f gilt aber auch:
2) f(x0) ist definiert, genau dann wenn c(x0,x0) nicht in H, also wenn
M angewendet auf x0 nicht haelt.
Diese beiden Aussagen sind aber widerspruechlich, weswegen solch eine
Maschine M gar nicht existieren kann!
QED
Satz 36: Das Halteproblem ist semientscheidbar.
Beweis: Gegeben z:N, so bestimme man x,y mit z=c(x,y) und simuliere
die durch x codierte Turingmaschine auf der Eingabe y. Kommt diese
Simulation zum Ende, so gebe man 0 aus.
Dieses intuitive Berechnungsverfahren kann leicht als WHILE
o.ae. Programm formalisiert werden.
Satz 37: Eine Menge A ist entscheidbar, genau dann, wenn sowohl A, als
auch N \ A (Komplement von A) semi-entscheidbar sind.
Beweis: Ist A entscheidbar, so auch N \ A durch Vertauschen von 0 und
1. Mithin sind aber auch A und N\A semi-entscheidbar. Sind
andererseits sowohl A, als auch N\A semi-entscheidbar (vermoege der
Turingmaschinen M1 und M2), so erhaelt man ein Entschidungsverfahren
fuer A, indem man bei gegebenem x:N die Berechnungen M1(x) und M2(x)
parallel durchfuehrt. Genau eine von beiden muss irgendwann zum Halt
kommen und dies liefert dann die
gesuchte Antwort.
Satz 38 Es existieren primitiv rekursive
Funktionen T, U, derart, dass zu jeder (einstelligen) berechenbaren
Funktion f eine natuerliche Zahl e existiert, sodass gilt
f(x) = U(mu s.T(e,s,x))
Beweis: Wir definieren S(e,t,y,x) als
if "Turingmaschine codiert durch e angewendet auf Eingabe x terminiert
nach t Schritten mit Ergebnis y" then 0 else 1
Das ist offensichtlich LOOP berechenbar, also primitiv rekursiv.
Nun setzen wir
T(e,s,x) = S(e,pr1(s),pr2(s),x)
wobei pr1 und pr2 die Inversen der Paarungsfunktion sind, also
pr1(c(x,y))=x, pr2(c(x,y))=y.
und schliesslich
U(x) = pr2(x).
QED
Definition: Eine Menge A<=N ist rekursiv aufzaehlbar (r.e.), wenn es
eine totale berechenbare Funktion f:N->N gibt, sodass A = {x | es
existiert i:N mit f(i)=x}.
Die Funktion f zaehlt also die Elemente von A der Reihe nach auf.
Satz 38: Eine nichtleere Menge A ist rekursiv aufzaehlbar gdw sie
semi-entscheidbar ist.
Beweis: Wird A durch f aufgezaehlt, so laesst sich chi'_A(x) wie folgt
definieren:
chi'_A(x) = let t = mu t.if f(t) = x then 0 else 1 in
f(t)
Man zaehlt also solange auf, bis das gegebene x erwaehnt wird, ggf
nie. Ist umgekehrt chi'_A berechenbar und e der Code einer
entsprechenden Turingmaschine, so ist
f(n) = if T(e,x,n)=0 then U(n) else a0
eine Aufzaehlung von A, wobei a0 ein beliebiges fest gewaehltes
Element von A ist. QED
Definition: Seien A, B zwei Teilmengen von N. A laesst sich auf B
reduzieren, i.Z. A <= B, genauer gesagt many-one reduzieren, wenn es eine
totale berechenbare Funktion f gibt, sodass gilt:
x:A <==> f(x):B
Folgerung: Laesst sich A auf B reduzieren und ist B (semi) entscheidbar, so
ist auch A (semi)entscheidbar; ist dagegen A unentscheidbar, dann erst
recht B. Desgleichen fuer "nicht semi entscheidbar".
Beispiele: Sei K = {e | e codiert eine Turingmaschine, die bei Eingabe
e haelt}.
Es gilt K <= H.
Wir haben im Beweis von Satz 35 eigentlich gezeigt, dass K
unentscheidbar ist und dann die Unentscheidbarkeit des Halteproblems H
gefolgert vermoege der Reduktion f(e) = c(e,e).
Die Abkuerzung K fuer obige Menge ist Standard.
Sei H0 = {e | e codiert eine Turingmaschine, die bei leerer Eingabe
haelt}
Es ist H <= H0 vermoege der Reduktion
f(z) = "diejenige Maschine, die das Band mit pr2(z) vorinitialisiert
und dann pr1(z) simuliert".
Satz 39 (Satz von Rice): Sei P eine Eigenschaft von (einstelligen)
berechenbaren Funktionen auf N. P gelte weder fuer alle, noch fuer gar
keine berechenbaren Funktionen. Dann ist
A_P = {e | die von der Turingmaschine e berechnete
Funktion hat die Eigenschaft P}
unentscheidbar.
Beweis:
Fall 1: Die nirgends definierte Funktion Omega habe die Eigenschaft
P. Es muss ausserdem eine berechenbare Funktion q geben, welche die
Eigenschaft P nicht hat. Sei M eine Turingmaschine fuer q.
Jetzt definieren wir eine Reduktion von N\H0 auf A_P durch
f(e) = "Die Maschine, die die Eingabe x zwischenspeichert, sodann
e auf leeres Band anwendet und anschliessend M_q auf Eingabe x
simuliert."
Die durch f(e) berechnete Funktion ist ueberall undefiniert, hat also
die Eigenschaft P, falls e auf leerem nicht haelt. Haelt dagegen e auf
leerem Band, so verhaelt sich f(e) wie M und liegt amit in A_P. Somit
gilt in diesem Falle N\H0 <= A_P und A_P ist unentscheidbar.
Im anderen Falle zeigt man analog H0 <= A_P womit A_P ebenfalls
unentscheidbar ist.
QED.
Dieser Satz bedeutet also, dass keine nichttriviale semantische
Eigenschaft von Programmen ("berechnet eine bestimmte Funktion",
"verhaelt sich bei bestimmten Eigenschaften soundso", ... durch
Inspektion des Programmtexts entscheidbar ist.
Wir bemerken, dass manche semantischen Programmeigenschaften immerhin
semi-entscheidbar sind, etwa die Frage, ob zu bestimmten Testeingaben
ein bestimmter Wert herauskommt. Andere aber nicht, wie zum Beispiel
die Frage, ob ein gegebenes Programm bei einer bestimmten Eingabe
nicht terminiert. Der Satz von Rice-Shapiro (nicht in dieser VL)
charakterisiert diejenigen semantischen Programmeigenschaften P,
sodass A_P semi-entscheidbar (= r.e.) ist.
Satz (Kriterium von Rice-Shapiro): Ist P eine
Eigenschaft der berechenbaren Funktionen, sodass A_P = {e | die durch
e berechnete Funktion hat Eigenschaft P} r.e. ist, so muss folgendes
gelten:
Hat Funktion f die Eigenschaft P, so existiert eine endliche
Teilfunktion g von f (also g ist nur an endlich vielen Punkten
definiert und stimmt an diesen mit f ueberein), welche auch die
Eigenschaft P hat.
Die Zugehoerigkeit zu P bemisst sich also nach dem Werteverlauf an
endlich vielen Testpunkten.
Beweis: Sei widerspruchshalber P eine Eigenschaft, die obiges
Kriterium verletzt, gebe es also eine Funktion f mit Eigenschaft P so,
dass keine endliche Teilfunktion g von f die Eigenschaft P hat. Wir
koennen dann zeigen (N \ K) <= A_P, woraus folgt, dass A_P nicht
r.e. ist.
Wir definieren jetzt
w(x) = "diejenige Turingmaschine, die bei Eingabe t die Maschine x
fuer t Schritte auf Eingabe x simuliert und dann, falls diese
Berechnung noch nicht gehalten hat, f(t) ausgibt und ansonsten
undefiniert ist."
Wenn jetzt x : N \ K, dann haelt also x angewendet auf x fuer kein t
und somit ist w(x) ein Programm fuer die Funktion f. Damit aber liegt
w(x) in A_P.
Ist dagegen x : K, haelt also x angewendet auf x nach, sagen wir, t
Schritten, so berechnet w(x) die endliche Teilfunktion von f mit
Definitionsbereich eingeschraenkt auf {0,1,...,t}. Diese hat nach
Voraussetzung aber nicht die Eigenschaft P und somit ist dann w(x)
nicht in A_P.
Wir haben gezeigt x : N\K <=> w(x):A_P und es folgt, dass A_P nicht
r.e. sein kann. QED
Mit diesem Kriterium kann man zum Beispiel sehen, dass folgende
Probleme nicht einmal semi-entscheidbar sind:
{x | x berechnet eine gegebene totale Funktion f}
{x | x berechnet irgendeine totale Funktion}
In der Literatur ist unter "Satz von Rice-Shapiro" eine exakte
Charakterisierung der r.e. semantischen Programmeigenschaften bekannt,
die wir hier nicht bringen.
Schliesslich noch ein weiterer Nachtrag:
Wir schreiben, Kleene folgend, {e} fuer die durch e:N (in einem fest
gewaehlten Binaerformat) als Turingmaschine aufgefasst berechnete
partielle Funktion, also
{e}(x) = U(mu t.T(e,x,t))
Satz (s-m-n-Theorem): Es gibt eine primitiv rekursive (totale)
Funktion "curry" mit den folgenden Eigenschaften:
i) {curry(e)} ist total
ii) Fuer alle x,y:N gilt {{curry(e)}(x)}(y) = {e}(c(x,y)), wobei die eine
Seite genau dann definiert ist, wenn es die andere ist.
4 Weitere unentscheidbare Probleme
==================================
Im folgenden wollen wir weitere unentscheidbare Probleme vorstellen. Das
Postsche Korrespondenzproblem (PCP) ist das folgende:
Definition:
Geg.: Wortpaare (x1,y1),...,(xk,yk) fuer k:N und xi,yi:Sigma^+.
Gefragt: Gibt es eine endliche Folge von Indizes i1,i2,...,in: N,
so dass gilt: xi1xi2...xin = yi1yi2...yin?
Die Folge i1,...,in heisst Loesung des PCP.
Bsp.: Das PCP K = ((1,101),(10,00),(011,11)) hat die Loesung 1,3,2,3.
Bsp.: Das PCP K = ((1000,10),(1,0011),(0,111),(11,0)) hat genau eine
Loesung, und diese hat Laenge 495.
Satz: PCP ist semi-entscheidbar.
Beweis: Eine TM kann systematisch immer laengere Folgen von Indizes
aufzaehlen und testen, ob diese eine Loesung der Eingabe darstellen.
Dies stoppt, falls es Loesung existiert, aber nicht, falls keine existiert.
QED
Um Unentscheidbarkeit des PCP zu zeigen, definieren wir zunaechst eine
leicht Modifikation, genannt MPCP, und zeigen dann H <= MPCP <= PCP.
Definition: Eingabe wie bei PCP. Frage: Gibt es eine Loesung i1,...,in
mit i1=1?
Satz: MPCP <= PCP
Beweis: Seien $ und # neue Symbole, die im Alphabet des MPCP nicht
vorkommen. Fuer ein Wort w = a1..an sei
w^ = #a1#...#an#
w` = #a1#...#an
w' = a1#...#an#
Eine Eingabe K = ((x1,y1),...,(xk,yk)) bilden wir nun auf eine Eingabe
f(K) = ((x1^,y1`),(x1',y1`),...,(xk',yk`),($,#$))
fuer das PCP ab.
Zu zeigen: K besitzt eine Loesung mit i1=1 gdw. f(K) irgendeine Loesung
besitzt.
(=>) Sei i1,...,in mit i1=1 eine Loesung fuer K. Dann ist (1,i2+1,...
in+1,k+2) eine Loesung fuer f(K).
(<=) Sei i1,...,in eine Loesung fuer f(K). Da jedes yi mit # anfaengt,
aber unter den xi nur x1 mit # anfaengt, muss fuer eine Loesung j1,...,jm
fuer K gelten: j1=1. Genauso sieht man leicht: jm=k+2. Ausserdem gilt:
(1,i2-1,...,in-1) ist eine Loesung fuer K. QED
Satz: H <= MPCP
Beweis: Gegeben die Kodierung einer TM M = (Z,Sigma,Gamma,delta,z0,_,E)
und ein Eingabewort w: Sigma^*. Wir konstruieren daraus eine Instanz
f(M,w) des MPCP die eine Loesung hat gdw. M auf w haelt.
Als Alphabet waehlen wir Gamma u Z u {#}. Als erstes Wortpaar waehlen
wir (#,#_z0w_#). Somit muss jede Loesung damit beginnen. Die Idee ist,
eine Loesung fuer das MPCP eine Folge von Konfigurationen von M nachbauen
zu lassen. Dabei legt man mit der zweiten Komponente immer etwas vor, was
in der ersten Komponente nachgebaut werden muss. Ausserdem bestimmt die
erste Komponente, was in der zweiten in der naechsten Konfiguration passieren
darf.
Die weiteren Wortpaare sind:
1) Kopierregeln: (a,a) fuer alle a:Gamma u {#}
2) Transitionsregeln: fuer alle z:Z, a,b,c: Gamma
(za,z'c) falls delta(z,a) = (z',c,N)
(za,cz') falls delta(z,a) = (z',c,R)
(bza,z'bc) falls delta(z,a) = (z',c,L)
3) Blanks einfuegen: (#,_#) und (#,#_)
4) Loeschregeln: (aze,ze) und (zea,ze) fuer alle a:Gamma, ze:E
5) Abschlussregeln: (ze##,#) fuer alle ze:E
Zu zeigen: M haelt auf w gdw. f(M,w) eine Loesung 1,...,in hat.
(=>) Angenommen, M haelt auf w. Dann gibt es eine Folge von Konfigurationen
k0,...,kt, so dass gilt: k0 = z0w, kt ist eine Endkonfiguration und ki |-
ki+1 fuer alle i=0,..,t-1. Dann hat f(M,w) eine Loesung mit dem Loesungswort
#k0#k1#...#kt#kt'#kt''##..#ze##
wobei kt',kt'',... durch Loeschen von Nachbarsymbolen von ze in kt entstehen.
(<=) Aus einer Loesung 1,...,in fuer f(M,w) laesst sich in derselben Weise
eine endliche Folge von Konfigurationen bauen, die bezeugt, dass M auf w
haelt. QED
Korollar: PCP ist unentscheidbar.
Bem.: Die folgenden, speziellen Instanzen des PCP sind entscheidbar: PCP ueber
einem einelementigen Alphabet, PCP mit k=1 oder k=2. Unentscheidbar ist PCP
mit k >= 7, fuer 3 <= k <= 6 noch unbekannt.
Mithilfe des PCP lassen sich nun einige Fragestellungen bzgl. kontext-freier
Grammatiken als unentscheidbar beweisen, die bei regulaeren Sprachen noch
entscheidbar sind.
Satz: Gegeben zwei kontext-freie Grammatiken G1 und G2. Die folgenden
Probleme sind alle unentscheidbar.
(P1) L(G1) n L(G2) = 0?
(P2) |L(G1) n L(G2)| = unendlich?
(P3) L(G1) n L(G2) ist kontextfrei?
(P4) L(G1) <= L(G2)?
(P5) L(G1) = L(G2)?
Beweis(skizzen): Man kann zeigen: PCP <= P1, PCP <= P2, PCP <= P3, P1 <= P4,
P1 <= P5.
(PCP<=P1) Sei K = (x1,y1),...,(xk,yk) eine Instanz des PCP ueber Alphabet
0,1. Wir bauen zwei kontext-freie Grammatiken ueber dem Alphabet Sigma =
{0,1,a1,...,ak}.
G1 = S -> A$B
A -> a1Ax1 | ... | akAxk | a1x1 | ... | akxk
B -> -y1Ba1 | ... | -ykBak | -y1a1 | ... | -ykak
wobei -w die Spiegelung von w ist.
G2 = S -> a1Sa1 | ... | akSak | T
T -> 0T0 | 1T1 | $
Jetzt gilt: K hat die Loesung i1,...,in mit Loesungswort w, genau dann wenn
ain...ai1w$-wai1...ain: L(G1) n L(G2).
(PCP<=P2) Folgt daraus, dass K eine Loesung hat genau dann wenn K unendlich
viele Loesungen hat.
(PCP<=P3) Mithilfe des Pumping-Lemmas kann man zeigen, dass L(G1)nL(G2)
nicht kontext-frei ist. 0 ist jedoch kontext-frei.
(P1<=P4,P1<=P5) Dies benutzt die Tatsache, dass L(G1) und L(G2) sogar
deterministisch kontext-frei sind, und man somit Typ-2-Grammatiken fuer ihre
Komplemente angeben kann. QED
**************************
III. Komplexitaetstheorie*
**************************
1 Die Komplexitaetsklassen P und NP
-------------------------------------
In der Komplexitaetstheorie fragen wir nicht nur danach, ob eine Sprache
entscheidbar ist, sondern wir kategorisieren Probleme auch danach, wie
schwer es ist sie zu entscheiden.
Bsp.: Vergleiche das Endlichkeitsproblem fuer NEAs und fuer kontext-freie
Grammatiken. Intuitiv ist ersteres wesentlich leichter.
Als Mass fuer "Schwierigkeit" werden wir - wie ueblich - den Zeitverbrauch
eines Algorithmus als Funktion der Eingabelaenge ansehen. Als Zeiteinheit
verwenden wir einen elementaren Schritt einer Turing-Maschine. Nur gilt
zwar, dass Einband-TM dieselben Sprachen wie Mehrband-TM erkennen, letztere
aber mit weniger Schritten auskommen. Aus diesem Grund betrachten wie
Komplexitaetsklassen, die gross genug sind darueber hinwegzusehen.
Def. Polynomielle Turingmaschine: Eine deterministische TM M hat
polynomielle Laufzeit, wenn es ein Polynom p gibt, sodass die Maschine
M bei Eingabe x hoechstens p(|x|) viele Schritte rechnet.
Man definiert allgemeiner auch die Laufzeit einer beliebigen TM als
Funktion (z.B exponentiell, linear etc) der Eingabelaenge und studiert
auch Laufzeiten nichtdeterministischer Maschinen.
Bem.: Die Simulation einer Mehrband- durch eine Einband TM verursacht
quadratischen Overhead, daher ist es egal, ob man "polynomiell" fuer
Ein- oder Mehrband definiert.
Intuition fuer Polynome: Verdopplung der Eingabelaenge geht einher mit
Ver-k-fachung der Rechenzeit, wobei k fest
ist. Z.B. quadratische Laufzeit: Verdopplung der Eingabelaenge
-> Vervierfachung der Rechenzeit.
Dagegen exponentielle Laufzeit: Verlaengerung der Eingabelaenge um
Eins -> Doppelte Rechenzeit.
Definition: Ein Problem A <= Sigma* ist in der Komplexitaetsklasse P,
wenn es eine (deterministische) polynomielle TM M gibt mit A = L(M).
Gemeinhin wird "polynomiell" mit "praktisch durchfuehrbar"
gleichgesetzt. Haeufig sind "echte" Algorithmen mit einer cleveren
Idee polynomiell, waehrend blindes Durchprobieren exponentielle
Laufzeit hat.
Bsp.: Die Menge { Kodierung(G,w) | G eine CFG, w ein Wort, w: L(G) }
ist in P, da es den CYK-Algorithmus gibt. Laesst man da auch
kontext-sensitive Grammatiken zu, dann ist die Menge
hoechstwahrscheinlich nicht mehr in P.
Satz: Ist f:P, dann ist L LOOP-berechenbar.
Beweis: Sei M eine TM, die f in Zeit O(n^k) berechnet (dies gilt
offen- sichtlich fuer alle in P berechenbaren Funktione). Diese laesst
sich durch eine 1-Band-TM in Zeit O(n^2k) simulieren, dies wiederum
durch ein GOTO- Programm in Zeit O(n^2k), dies durch ein
WHILE-Programm mit einer WHILE- Schleife in Zeit O(n^2k). Da die
Laufzeit dieses Programms durch ein Polynom p'(n) beschraenkt ist,
laesst sich die WHILE-Schleife ersetzen durch y := p'(n); LOOP y
DO. Da Addition und Multiplikation LOOP- berechenbar ist, ist somit
auch f LOOP-berechenbar. QED
Als naechstes definieren wir NP, die nichtdeterministische Variante von
P.
Beispiele fuer Probleme in P: Grundrechenarten auf den natuerlichen
Zahlen ("Ist das i-te Bit von x +-*/ y gleich 1?"). Loesen linearer
Gleichungssysteme. Kuerzeste Wege in Graphen ("Ist der kuerzeste Weg
hoechstens k lang? Fuehrt er ueber x?"). Schedulingprobleme: Gegeben
Aufgaben mit Start- und Endzeiten. Wie kann man moeglichst viele
Auftraege abarbeiten?
Beispiele fuer Probleme, von denen man nicht weiss, ob sie in P sind:
Finden einer kuerzesten Rundreise (alle Staedte besuchen), optimale
Stundenplanung, Graphenfaerbung, Schedulingprobleme: Gegeben Auftraege
mit Dauern (Zeitpunkt egal). Wie kann man moeglichst viele abarbeiten?
Aequivalent: Waescheleinenproblem.
Definition: Komplexitaetsklasse NP: Ein Problem A <= Sigma* ist in der Klasse NP, wenn es ein Problem B in P, sowie ein Polynom p gibt, derart dass
x:A <==> es existiert y mit |y| <= p(|x|) und (x,y):B
Interpretation: x:A gdw eine "Loesung" y existiert und man kann in
polynomieller Zeit verifizieren, ob ein vorgelegtes Wort "Loesung" zu
gegebener Instanz ist. Loesungen duerfen nur polynomielle Laenge
haben.
Bem: Trivialerweise gilt: Wenn A:P dann auch A:NP.
Bem: Traditionell wird NP ueber nichtdeterministische polynomielle TM
definiert. Mit Nichtdeterminismus kann man ja die "Loesung" raten.
Bsp.: Ein Hamilton-Kreis in einem ungerichteten Graphen ist eine Tour
durch den Graphen, die jeden Knoten genau einmal besucht. Ein Euler-
Kreis ist eine Tour, die jede Kante genau einmal besucht. Es gilt:
1) { G | G hat Euler-Kreis } : P
2) { G | G hat Hamilton-Kreis } : NP (und vermutlich nicht in P)
zu 1) G hat Euler-Kreis genau dann, wenn jeder Knoten gerade Grad hat.
Dies kann offensichtlich von einer det. TM in polynomialer Zeit
getestet werden. zu 2) Ein vorgelegter Hamilton-Kreis ("Loesung")
kann offensichtlich in polynomieller Zeit erkannt werden.
Bem.: Offensichtlich gilt P <= NP. Ob P=NP gilt, ist seit ca. 1970
unbekannt und wird auch als das groesste Problem der theor. Informatik
bezeichnet.
Analogie: P =~= Entscheidbar, NP =~= Semi-entscheidbar
Leider ist es bisher nicht moeglich, ein Problem in NP \ P anzugeben.
Dennoch kann man, sozusagen proaktiv, Reduktionen betrachten:
Definition (Klasse FP): Eine Funktion f:Sigma* -> Sigma* ist in
polynomieller Zeit berechenbar, kurz f : FP, wenn es eine polynomielle
Turingmaschine gibt, die f berechnet. (Bei Eingabe w haelt die
Maschine irgendwann an (nach p(|w|) Schritten) und auf dem Band steht
dann f(w).
Satz: Sind f, g:FP, so auch die Komposition h(x)=g(f(x)).
Beweis: Seien p, q Polynome, die die Laufzeit von Maschinen fuer f bzw
g beschraenken. Wir koennen annehmen, dass p und q monoton sind, ggf
durch Weglassen von Monomen mit negativen Koeffizienten. Die
offensichtliche Maschine, die h berechnet hat nun bei gegebener
Eingabe x eine Laufzeit T(x), die durch
p(|x|) + q(|f(x)|) + c.(|x| + |f(x)|)
fuer eine Konstante c nach oben abgeschaetzt werden kann. Nun gilt
|f(x)| <= p(|x|) da ja die einzelnen Symbole der Ausgabe f(x) im
Rahmen der Rechenzeit eins nach dem anderen hingeschrieben werden
muessen. Somit gilt fuer die Gesamtrechenzeit
T <= p(|x|) + q(p(|x|)) + c.(|x| + p(|x|))
Das aber ist ein Polynom in |x|. QED
Definition: A<= Sigma*, B<=Sigma*. Das Problem A ist polynomiell reduzierbar auf das Problem B, i.Z. A <=P B, wenn es eine Funktion f:FP gibt, sodass
x:A <==> f(x):B
Wenn A <=P B und B:P so folgt A:P. Ausserdem folgt aus A <=P B und B
<=P C, dass A <=P C.
Definition: Ein Problem B ist NP-schwer (auch NP-hart), wenn
A <=P B
fuer alle Probleme A in NP erfuellt ist. Ein Problem B ist
NP-vollstaendig, wenn es NP-schwer ist und zusaetzlich selbst in NP
liegt.
NP-vollstaendige Probleme sind also diejenigen Probleme in NP, die
bzgl. <=P maximalen Schwierigkeitsgrad haben.
Zum Beispiel ist das folgende (entscheidbare) Problem NP-hart:
EVAL = {(P,x) | P ist ein LOOP Programm, welches bei Eingabe x Ergebnis 1 liefert}
Ist naemlich A in NP, so ist die charakteristische Funktion von A
leicht LOOP berechenbar. Liegt die Eingabe x vor, so ist die Zahl der moeglichen Loesungen durch |Sigma|^p(|x|) beschraenkt und man kann mit geschachtelten LOOP-Schleifen alle moeglichen Loesungen durchprobieren und pruefen. Sei P das
entsprechende LOOP Programm. Die Funktion
f(x) = (P,x)
ist in FP und liefert eine Reduktion von A auf EVAL.
Das Problem EVAL ist aber selbst nicht in NP, daher nicht NP-vollstaendig.
Das Erfuellbarkeitsproblem
--------------------------
Wir fixieren eine endliche Menge von Variablen V, die Werte in {0,1}
(0 = falsch, 1 = wahr) annehmen sollen.
Ein Literal ist entweder eine Variable x:V oder eine negierte
Variable ~x. Es gibt also zweimal soviele Literale wie Variablen.
Eine Klausel ist eine Menge von Literalen {l1,..,lk}. Man versteht
eine Klausel als die Disjunktion ("oder") ihrer
Variablen. Dementsprechend verwendet man auch die Notationen
l1 v ... v lk
l1 | ... | lk
Die leere Klausel bezeichnet Falschheit.
Beispiele mit V ={x,y,z,w}:
~x | ~y | w
~x | y | w
x
~y
Die ersten beiden Klauseln kann man auch in der Form
x&y -> w
x -> y|w
schreiben, denn ~x|~y|w bedeutet ja gerade, dass wenn x und y wahr
sind, dann auch wahr sein muss.
Eine konjunktive Normalform ist gegeben durch eine Menge von
Klauseln.
Eine Belegung ist eine Funktion eta:V->{0,1}, die also jeder
Variablen einen Wahrheitswert zuordnet. Eine Belegung eta erfuellt
eine Klausel k, wenn es ein Literal l in k gibt, sodass eta(l)=1. Man
setzt hierbei eta(~x)=1-eta(x). Die Belegung erfuellt eine KNF K, wenn
sie alle Klauseln in K erfuellt.
Das Erfuellbarkeitsproblem fuer konjunktive Normalform, kurz
KNF-SAT besteht darin, zu gegebener KNF festzustellen,
ob es eine Belegung gibt, die sie erfuellt:
KNF-SAT:
Gegeben: Eine endliche Menge von Variablen V und eine KNF K ueber V.
Gefragt: Existiert eine Belegung, die K erfuellt.
Diese "Gegeben-Gefragt"-Spezifikation definiert KNF-SAT formal als die
Menge aller Paare (V,K), geeignet codiert als Woerter ueber einem
bestimmten Alphabet, sodass eine erfuellende Belegung fuer K
existiert. Die "Gegeben-Gefragt" Notation abstrahiert von der Wahl der
Codierung, vom Alphabet und auch von der Formalisierung eines
"Problems" als Sprache ueber einem Alphabet.
Satz: KNF-SAT ist in NP.
Bemerkung: Hat man ein Entscheidungsverfahren fuer KNF-SAT, so kann
man ohne grossen Zusatzaufwand auch eine erfuellende Belegung
bestimmen. Hierzu setzt man zunaechst die erste Variable x1 auf 0 und
berechnet die Klauselmenge, die man erhaelt, indem man alle Literale
x entfernt und alle Klauseln loescht, die das Literal ~x
enthalten. Ist die resultierende Klauselmenge noch erfuellbar, so kann
man mit x2 weiterfahren, ansonsten muss x1=1 die richtige Setzung
gewesen sein und man ersetzt entsprechend jedes Vorkommen von x1 durch
1, vereinfacht und arbeitet weiter.
Viele andere Probleme lassen sich auf KNF-SAT polynomiell reduzieren,
indem man die moeglichen Loesungen durch die Variablenbelegungen
repraesentiert und die Klauseln dazu nutzt, die problemspezifischen
Einschraenkungen zu formulieren.
Beispiel:
3-COL:
Gegeben ist ein ungerichteter Graph G = (V,E). V ist die Knotenmenge, E
<= VxV die Menge der Kanten.
Gefragt: Gibt es eine Zuordnung von Farben c:{r, w, b} zu den Knoten
derart, dass keine durch eine Kante verbundene Knoten dieselbe Farbe
erhalten?
Es gilt 3-COL <=P KNF-SAT. Ist naemlich ein Graph G = (V,E) gegeben, so
konstruiert man wie folgt eine Instanz f(G) von KNF-SAT: Fuer jeden Knoten e
fuehrt man drei Variablen ein: er, ew, eb, sowie die Klauseln
{er,ew,eb}, {~er, ~ew}, {~er, ~eb}, {~ew, ~eb}
Diese stellen sicher, dass genau eine der drei Variablen gesetzt ist
(auf 1). Zusaetzlich fuehrt man fuer jede Kante e-f die Klauseln
{~er,~fr}, {~ew,~fw}, {~eb, ~fb} ein, wodurch sichergestellt ist, dass
verbundene Knoten nicht dieselbe Farbe bekommen.
Aehnlich zeigt man HAMILTON <=P KNF-SAT:
Fuer jede
Kante (u,v) in E fuehrt man eine Variable x(u,v) ein. Die Idee ist,
dass diejenigen Kanten (u,v), fuer die x(u,v)=1 einen Hamiltonschen
Kreis bilden. Die Klauseln sollen gerade das sicherstellen:
1) Zu jedem Knoten v gibt es Knoten u1, u2, sodass x(u1,v)=1 und
x(v,u2)=1:
Hierzu fuehren wir fuer jeden Knoten v eine eigene Klausel ein,
deren Literale gerade die x(u1,v),x(v,u2) sind. Deren Anzahl ist
|V|^2.
2) Jeder Knoten kommt hoechstens in zwei Kanten vor und zwar einmal
links und einmal rechts:
Hierzu fuehren wir fuer je vier Knoten v,u1,u2,u3 die folgenden zwei
Klauseln ein:
~x(u1,v) | ~x(v,u2) | ~x(v,u3)
~x(u1,v) | ~x(v,u2) | ~x(u3,v)
Die Anzahl dieser Klauselpaare ist also |V|^4
Erfuellt eine Belegung alle genannten Klauseln, so definiert sie einen
Hamiltonschen Pfad, insbesondere ist also die erzeugte Klauselmenge
erfuellbar genau dann wenn im gegebenen Graphen ein Hamiltonscher
Kreis existiert. Sicherlich ist die konstruierte Klauselmenge in
polynomieller Zeit berechen- und hinschreibbar, sodass tatsaechlich
eine Reduktion definiert wurde. Es gilt in der Tat auch KNF-SAT <=P
HAMILTON; das ist aber deutlich schwerer nachzuweisen.
Auf aehnliche Weise lassen sich auch andere viele andere
kombinatorische Probleme als KNF-SAT Instanzen kodieren. In der Tat
kann man KNF-SAT als eine Art Spezifikations- oder Programmiersprache
fuer solche Probleme auffassen.
NP Vollstaendigkeit von KNF-SAT
-------------------------------
Satz ("Satz von Cook"): KNF-SAT ist NP-vollstaendig.
Beweis: Sei A:NP und x:A <==> existiert y. |y|<=p(|x|) & (x,y):B,
wobei p ein Polynom ist und B:P. Sei M eine polynomielle TM fuer
B.
Wir muessen eine Reduktion A <=P KNF-SAT konstruieren.
Sei also x:Sigma* gegeben. Wir bestimmen n so, dass die Laufzeit, wie auch die Groesse der Bandinhalte einer Berechnung von M auf Eingabe (x,y) mit |y|<=p(|x|) durch n beschraenkt ist. Es gilt n = q(|x|) fuer ein festes Polynom q.
Wir repraesentieren Bandinhalte als Woerter der Laenge n.
Wir fuehren nun die folgenden Variablen ein:
1) Fuer Zustand z, Zeitpunkt t (0 <= t <= n) eine Variable
zust(t,z) ("Zustand zum Zeitpunkt t ist z")
2) Fuer Zeitpunkt t (0 <= t <= n) und Bandposition p (-n <= p <= n) eine
Variable kopf(t,p) ("Kopf steht zum Zeitpunkt t an Position p")
3) Fuer Bandsymbol a:Gamma, Zeitpunkt t (1<=t<=n) und Bandposition p
(-n <= p <= n) eine Variable band(t,p,a) ("Bandinhalt zum Zeitpunkt t an
Position p ist a")
Man beachte, dass die Zahl der eingefuehrten Variablen ein Polynom in
n und somit auch in |x| ist. Genauer gesagt ist sie (n+1)*|Z| + (n+1)(2n+1)
Es ist klar, dass jeder Folge von Konfigurationen der Laenge n eine
Belegung dieser Variablen entspricht und umgekehrt. Durch die
folgenden Klauseln stellen wir jetzt sicher, dass nur solche
Belegungen infrage kommen, die eine akzeptierende Berechnung der
Laenge n von Eingabe x aus kodieren. Ist die resultierende
Klauselmenge noch erfuellbar, so gibt es eine akzeptierende
Berechnung, also x:A und umgekehrt. Die erforderlichen Klauseln sind
wie folgt:
1) Fuer -n<=p<=n Klauseln mit den Variablen band(0,p,a), welche
besagen, dass der initiale Bandinhalt von der Form (x,y) ist fuer
ein beliebiges y mit |y|<=p(|x|).
2) Die Klausel kopf(0,1) ("Zu Beginn steht der Kopf auf Position 1.")
3) Fuer -n <= i1 < i2 <= n und 0 <= t <= n die Klausel ~kopf(t,i1) v
~kopf(t,i2) (Der Kopf steht jeweils an hoechstens einer Stelle)
4) Fuer -n <= i < n und 0 <= t <= n und a1, a2 : Gamma mit a1 =/= a2
die Klausel ~band(t,i,a1) v ~band(t,i,a2) (Hoechstens ein Symbol
an jeder Bandposition und Zeitpunkt)
5) Die Klausel zust(n,z_A), wobei z_A der akzeptierende Zustand ist.
("Am Ende der Rechnung wurde akzeptiert")
6) Fuer 0<=t<n, -n<=p<=n, Zustand z, Symbol a eine Klauselmenge, die
der folgenden aussagenlogischen Formel entspricht:
zust(t,z) & band(t,p,a) & kopf(t,p) ->
\/_((z',b,d):delta(z,a) (kopf(t+1,p+d) & band(t+1,p,b) & zust(t+1,z')
wobei diesmal d:{-1,0,1} statt {L,R,N} gewaehlt wird. Sollte p+d
nicht im Bereich -n..n liegen, so lassen wir das entsprechende
Disjunkt weg.
Man erhaelt die gewuenschte Klauselmenge durch Anwenden der de
Morganschen Regeln, z.B.
A&B -> (U&V | W&Z) =
~A | ~B | (U&V) | (W&Z) =
(~A|~B|U|W)&(~A|~B|U|Z)&(~A|~B|V|W)&(~A|~B|V|Z)
Es entstehen also hier 4 Klauseln. In der obigen Anwendung
entstehen jeweils 3^(|delta(z,a)|) viele Klauseln, was eine feste,
von |x|, unabhaengige Groesse ist und somit polynomial in |x|.
7) Fuer 0 <= t < n, -n <= p <=n und Symbol a die Klausel
band(t,p,a) & ~kopf(t,p) -> band(t+1,p,a)
bzw. als Disjunktion geschrieben:
~band(t,p,a) | kopf(p) | band(t+1,p,a)
("Diejenigen Bandpositionen, an denen sich der Kopf nicht befindet,
bleiben stehen.")
Es ist jetzt aufgrund der Konstruktion klar, dass die genannte
Klauselmenge genau dann erfuellbar ist, wenn eine akzeptierende
Berechnung existiert. Damit ist die verlangte Reduktion von A auf
KNF-SAT gegeben. QED
3.2.3: Weitere NP-vollstaendige Probleme:
3KNF-SAT: Gegeben eine Menge von Klauseln mit jeweils genau 3
Literalen. Gefragt ist nach der Erfuellbarkeit dieser Klauselmenge.
Satz: 3KNF-SAT ist NP-vollstaendig.
Beweis: Es genuegt zu zeigen KNF-SAT <=P 3KNF-SAT. Hat man eine
Klausel l1|...|lk gegeben, so fuehrt man neue Variablen qi ein und
fuehrt folgende Dreierklauseln ein:
~l1|q1, ~q1|l1 ("q1 = l1")
~q1|q2, ~l2|q2, ~q2|q1|l2 ("q2 = q1|l2")
~q2|q3, ~l3|q3, ~q3|q2|l3 ("q3 = q2|l3")
...
... ("qk = q(k-1)|lk")
und nimmt schliesslich noch die Klausel qk hinzu, deren Wahrheitswert
ja gerade der Disjunktion der li entspricht. QED
SAT: Ist eine gegebene aussagenlogische Formel erfuellbar?
Satz: SAT ist NP-vollstaendig.
Beweis: Klarerweise ist KNF-SAT <=P SAT, somit ist SAT NP-hart. Auf
der anderen Seite ist SAT natuerlich in NP, da ja eine geratene erfuellende
Belegung in polynomialer Zeit bestaetigt werden kann. QED
Man kann SAT auch direkt auf 3KNF-SAT reduzieren, indem man fuer jede
Teilformel eine frische Variable einfuehrt und wie beim letzten Beweis
durch 3er-Klauseln sicherstellt, dass diese die gewuenschte Belegung
erfaehrt. Was man nicht machen kann, ist die aussagenlogische Formel
durch Umformungen auf konjunktive Normalform zu bringen, da sich dabei
die Groesse u.U. exponentiell aufblaeht. Es handelte sich dabei also
nicht um eine in polynomialer Zeit berechenbare Reduktion.
Interessanterweise ist das Problem 2KNF-SAT in P.
Ab jetzt werden wir ein kanonisches Beispiel einer 3KNF-SAT zur
Illustration weiterer NP-Vollstaendigkeitsbeweise verwenden:
F = {k1, k2, k3} (3 Klauseln)
k1 = x1 v ~x3 v x5
k2 = ~x1 v x5 v x4
k3 = ~x2 v ~x2 v ~x5
x3 -> x1 v x5
x1 -> x4 v x5
x2 -> x5
in fuenf Variablen x1,x2,x3,x4,x5.
MENGENUEBERDECKUNG:
Gegeben: Ein System von n Teilmengen S1..Sn einer endlichen Menge T und eine
Zahl k <= n. Gefragt: Existiert eine Auswahl von k Teilmengen Si1..Sik deren
Vereinigung bereits ganz T ergibt?
Satz: MENGENUEBERDECKUNG IST NP-vollstaendig.
Beweis: Dass MENGENUEBERDECKUNG in NP ist, ist klar: Hat man eine
entsprechende Auswahl der Teilmengen vorgegeben, so faellt die
Ueberpruefung leicht. Umgekehrt konstruieren wir eine Reduktion von
KNF-SAT auf MENGENUEBERDECKUNG. Seien also m Klauseln K1..Km gegeben,
in den Variablen x1..xn.
Fuer jede Variable xj fuehren wir jetzt zwei Mengen Sj und Sj' ein. Die Idee ist,
dass wenn eine Ueberdeckung Sj beinhaltet, dann xj=1 genommen werden
kann und wenn Sj' ausgewaehlt wird, dann xj=0 genommen werden kann um
eine erfuellende Belegung zu erhalten.
Sj = {i | 1<=i<=m, xj kommt in Ki positiv vor} u {m + j}
Sj' = {i | 1<=i<=m, xj kommt in Ki negativ vor} u {m + j}
T = {1,...,m+n}
Gesucht ist eine Ueberdeckung mit hoechstens n (Zahl der Variablen)
Mengen.
Da ja die Zahlen m+j ueberdeckt werden muessen, muss eine Ueberdeckung
fuer jedes j<=n entweder Sj oder Sj' aber nicht beide enthalten.
Das Ueberdecken eines 1<=i<=m bedeutet aber, dass unter der
zugeordneten Belegung die Klausel i erfuellt wird. Also entsprechen
Ueberdeckungen mit n Mengen genau den erfuellenden Belegungen. QED
Im Beispiel waere
S1 = {1,4}
S1' = {2,4}
S2 = {5}
S2' = {3,5}
S3 = {6}
S3' = {1,6}
S4 = {2,7}
S4' = {7}
S5 = {1,2,8}
S5' = {3,8}
CLIQUE: Gegeben: ein (ungerichteter) Graph G = (V,E) und eine Zahl
k. Gefragt: Besitzt G eine Clique der Groesse k (oder mehr). Eine
Clique ist eine Teilmenge von Knoten, so dass je zwei verschiedene
Knoten aus der Teilmenge ueber eine Kante verbunden
sind. (Kante=befreundet sein, Clique=jede(r) mit jede(r,m)
befreundet.)
Satz: CLIQUE ist NP-vollstaendig. Dass CLIQUE in NP ist, ist
klar. Fuer die NP-Haerte verwenden wir eine Reduktion von
3KNF-SAT. Sei l(i,k), i=1..m, k=1..3 das k-te Literal der i-ten
Klausel in einer Klauselmenge C.
Wir konstruieren einen Graphen mit den Knoten {(i,k) | i=1..m, k=1..3}
und verbinden (i,k) mit (i',k'), wenn i=/=i' und ausserdem l(i,k) und
l(i',k') sich nicht gegenseitig ausschliessen. Dieser Graph hat eine
Clique der Groesse m genau dann wenn C erfuellbar ist. Ist naemlich
eine erfuellende Belegung gegeben, so waehlt man aus jeder Klausel i ein
erfuelltes Literal k aus. Die l(i,k) bilden dann eine Clique der
Groesse m. Umgekehrt muss eine Clique der Groesse m fuer jedes i einen
Knoten (i,m_i) beinhalten. Man setzt nun eine Belegung eta so fest,
dass eta(l(i,m_i)) = 1 wird. QED
Im Beispiel gaebe es also 9 Knoten (i,k) mit i=1,2,3 und
k=1,2,3. Es gibt eine Verbindung von (2,1) nach (3,2), da das 1-te
Literal in k2 ~x1 ist und das 2-te Literal in k3 ~x2 ist. Die beiden
sind aber kompatibel. Andererseits gibt es keine Verbindung von (1,1)
nach (2,1) da die entsprechenden Literale x1 und ~x1 inkompatibel
sind.
VERTEX-COVER: Gegeben ungerichteter Graph G=(V,E) und eine Zahl
k. Gefragt: Gibt es eine Auswahl U<=V von hoechstens k Knoten, sodass jeder
Kante einen der ausgewaehlten Knoten enthaelt?
Satz: VERTEX-COVER ist NP-vollstaendig. VERTEX-COVER in NP ist
klar. Ausserdem gilt CLIQUE <=P VERTEX-COVER vermoege der Reduktion
f(V,E) = ((V, Komplement von E), |V|-k).
Es gilt: (V,E) besitzt eine Clique C der Groesse k <=>
Im Komplementgraphen sind die Knoten von C paarweise nicht verbunden <=>
Die Menge V \ C bildet eine Ueberdeckung. QED
RUCKSACK: Gegeben natuerliche Zahlen a1..an und b. Gefragt: gibt es
eine Teilmenge I <= {1,...,n} sodass summe{a_i | i:I} = b.
Beachtung: die Laenge der ai und b in der Binaerdarstellung geht hier
in die Problemgroesse ein.
Satz: RUCKSACK ist NP vollstaendig.
Beweis: RUCKSACK in NP ist klar. Fuer die Haerte geben wir eine
Reduktion 3KNF-SAT <= RUCKSACK an.
Sei eine Instanz von 3KNF-SAT mit m Klauseln k1..km und n Variablen
x1..xn gegeben. Die Zahlen a_i und b, die wir konstruieren haben alle
m + n Stellen im Zehnersystem.
Fuer jede Variable xj fuehren wir zwei Zahlen uj und vj ein. Hierbei
hat
uj eine 1 in der i-ten Position, wenn xj in ki positiv vorkommt und
eine 1 in der m+j-ten Position.
vj eine 1 in der i-ten Position, wenn xj in ki negativ vorkommt und
eine 1 in der m+j-ten Position.
Ausserdem gibt es noch Zahlen
ci mit einer 1 in der i-ten Position
di mit einer 2 in der i-ten Position.
Die Zahlen haben 0-er in allen nicht explizit erwaehnten Positionen.
Aus diesen Zahlen laesst sich eine Auswahl zu
444....444111....111
`--------´`--------´
m n
summieren genau dann, wenn die gegebene 3KNF erfuellbar ist.
Im Beispiel haben wir die Zahlen
u1 = 100 10000
u2 = 000 01000
u3 = 000 00100
u4 = 010 00010
u5 = 110 00001
v1 = 010 10000
v2 = 001 01000
v3 = 100 00100
v4 = 000 00010
v5 = 001 00001
c1 = 100 00000
c2 = 010 00000
c3 = 001 00000
d1 = 200 00000
d2 = 020 00000
d3 = 002 00000
PARTITION: Gegeben natuerliche Zahlen a1..ak. Gefragt: gibt es eine
Teilmenge I <= {1..k} sodass summe{a_i | i:I} = summe{ai | i nicht in
I}.
Satz: PARTITION ist NP-vollstaendig.
Beweis: PARTITION <=P RUCKSACK, also PARTITION in NP. Umgekehrt gilt
aber auch RUCKSACK <=P PARTITION wie folgt: Sei (a1..ak,b) eine
Instanz von RUCKSACK und M=summe{ai | i=1..k}. Die Instanz
(a1,...,ak,M-b+1,b+1) von PARTITION hat eine Loesung genau dann, wenn
die gegebene Instanz von RUCKSACK eine Loesung besitzt. QED
BIN-PACKING: Gegeben n natuerliche Zahlen a1..an und zwei weitere natuerliche Zahlen
b und k. Gefragt: Koennen die Zahlen a1..an so in hoechstens k Gruppen
aufgeteilt werden, dass die Summe der Zahlen in jeder Gruppe <= b
ist. Deutung: b = Behaeltergroesse, k = Zahl der Behaelter.
Satz: BIN-PACKING ist NP-vollstaendig.
Beweis: BIN-PACKING in NP ist klar. Fuer die Haerte reduzieren wir
PARTITION auf BIN-PACKING:
(a1..ak) |-> Behaeltergroesse b = summe{ai | i=1..k} / 2 (ggf alles
mit 2 durchmultiplizieren),
Zahl der Behaelter k = 2
Objekte: a1,...,ak.
QED
DIR-HAMILTON: Gegeben: ein gerichteter Graph G=(V,E). Gesucht: eine
Bijektion pi:{1,...,|V|}->V sodass gilt: pi(i)->pi(i+1) ist eine Kante
fuer alle i=1..|V|-1 und ausserdem ist pi(|V|)->pi(1) eine Kante. Mit
anderen Worten ist ein geschlossener Kantenzug gesucht, der jeden
Knoten genau einmal besucht.
Satz: DIR-HAMILTON ist NP-vollstaendig.
Beweis: DIR-HAMILTON in NP ist klar. Fuer die Haerte reduzieren wir
von 3-KNF-SAT aus. Details siehe Schoening. QED
HAMILTON: Dasselbe wie DIR-HAMILTON, nur fuer ungerichtete Graphen.
Satz: HAMILTON ist NP-vollstaendig.
Beweis: Man reduziert DIR-HAMILTON auf HAMILTON. Details siehe
Schoening.
TRAVELLING-SALESMAN: Gegeben: eine n x n Matrix mit Eintraegen aus N
und eine Zahl k. Gefragt: gitb es eine Permutation pi:{1..n}->{1..n}
sodass M(pi(1),pi(2)) + M(pi(2),pi(3)) + .. + M(pi(n-1),pi(n)) +
M(pi(n),pi(1)) <= k ? Deutung: Es seien n Staedte in einer bestimmten
Reihenfolge zu besuchen. M(i,j) gibt die Entfernung der Stadt i von j
an. Gibt es eine Rundreise, der Gesamtlaenge kuerzer als k ist?
Satz: TRAVELLING-SALESMAN ist NP-vollstaendig.
Beweis: Triviale Reduktion von HAMILTON.
3-FAERBBARKEIT: Gegeben ein ungerichteter Graph G=(V,E). Gefragt: Gibt es eine
Funktion f:V->{1,2,3} sodass fuer jede Kante {u,v}:E gilt f(u) =/=
f(v). Deutung: Lassen sich die Knoten so mit 3 Farben einfaerben, dass
keine zwei beanchbarten Knoten dieselbe Farbe erhalten.
Satz: 3-FAERBBARKEIT ist NP-vollstaendig.
Beweis: Durch Reduktion von 3KNF-SAT an. Details siehe Schoening.
IV Logik
--------
1. Die Arithmetik.
Terme sind durch folgende Grammatik definiert:
Tm ::= x | 0 | 1 | Tm + Tm | Tm * Tm
Hierbei rangiert x ueber eine abzaehlbar unendliche MEnge von
Variablen, z.B. x1,x2,x3,x4,x5,...
Formeln der Arithmetik sind durch folgende Grammatik definiert:
Fo ::= Tm = Tm | All x.Fo | Ex x.Fo | Fo&Fo | ~Fo | Fo v Fo | Fo->Fo
Zum Beispiel ist phi := Ex z.x+z=y eine Formel.
Man definiert in offensichtlicher Weise die freien Variablen einer
Formel. ZumBeispiel hat phi die freien Variablen x und y. Die
Bedeutung einer Formel haengt von der Belegung der freien Variablen
ab. Alle Variablen rangieren ueber natuerliche Zahlen; die
Bedeutung der Symbole +, 0, 1, =, &, v, ->, All, Ex ist die
allgemein uebliche. Hat zum Beispiel x den Wert 7 und y den Wert
10, so ist phi wahr, da ja zum Beispiel z=3 gewaehlt werden
kann. Im allgemeinen ist phi wahr, genau dann wenn der Wert von x
kleiner oder gleich dem Wert von y ist. Man schreibt kurz
phi(x,y) <=> x<=y
und sagt, phi definiere (in der Arithmetik) die kleiner oder gleich Relation.
Ebenso laesst sich die Relation z = x DIV y definieren durch
Ex r. x = z*y+r & r+1 <= y
wobei natuerlich <= durch die obige Formel phi zu ersetzen ist.
Ist irgendeine Relation (in der Arithmetik) definierbar, so
erlauben wir uns so aehnlich wie bei den LOOP Programmen, sie
direkt in Formeln zu verwenden.
Ist der Graph einer Funktion definierbar, wie etwa der Graph der
Funktion DIV in obigem Beispiel, so erlauben wir uns auch die
Verwendung solch einer Funktion in Termen. Zum Beispiel ist
All x.All y. y * (x DIV y) <= x
eine Abkuerzung fuer
All x.All y.Ex m.(m = x DIV y) & y * m <= x
und im uebrigen eine wahre Aussage.
Satz: Ist f:N^n->N berechenbar, so ist {(y,xs) | f(xs)=y}
in der Arithmetik definierbar.
Beweis: Siehe Schoening oder als Uebung.
Eine Formel, die keine freien Variablen enthaelt heisst Satz. Ein
Satz ist entweder wahr oder falsch.
Korollar: Die Menge aller wahren Saetze ist nicht rekursiv
aufzaehlbar.
Beweis: Sei f(x) = 0, falls x:K (x angewandt auf x haelt) und
undefiniert sonst. f ist berechenbar, also gibt es eine Formel
phi(x) sodass phi(n) wahr ist, genau dann wenn n:K. Hierbei
bezeichnet phi(n) den Satz, den man aus phi erhaelt, indem man
jedes Vorkommen von x durh 1+...+1 (n Mal) ersetzt.
Somit ist aber ~phi(n) wahr, genau dann, wenn n nicht in K. Waere
nun die Menge der wahren Saetze r.e., so auch N\K, was nicht der
Fall ist.
Das aber bedeutet, dass es keinen formalisierten Beweisbegriff
geben kann, mit dem alle wahren Saetze der Arithmetik bewiesen
werden koennen. Was ist eigentlich ein formalisierter Beweis ? Nun,
wir koennen sagen, dass ein Beweissystem einfach eine
entscheidbare Relation Bew auf N * N ist, wobei Bew(n,f) bedeuten
soll, dass n einen Beweis codiert (in einem geeigneten
Binaerformat), der den durch f codierten Satz der Arithmetik
beweist.
Das Beweissystem sollte korrekt sein in dem Sinne, dass aus
Bew(n,f) folgt, dass der durch f codierte Satz wahr ist.
Gibt es auch umgekehrt fuer jeden Satz f einen Beweis, also ein n:N
mit Bew(n,f), so ist das Beweissystem vollstaendig. Wir haben
soeben gezeigt, dass es fuer die Arithmetik kein vollstaendiges
Beweissystem gibt. Das ist der Goedelsche Unvollstaendigkeitssatz.
Goedel selbst ist beim Beweis seines Theorems etwas direkter und
aus philosophischer Sicht vielleicht interessanter vorgegangen. Er
gibt sich ein beliebiges korrektes Beweissystem vor und
argumentiert, dass die Relation Bew in dr Arithmetik definierbar
ist. Er argumentiert weiter, dass die Funktion subst definiert
durch
subst(f,n) = Code desjenigen Satzes, den man durch Einsetzen
von 1+...+1 (n Mal) fuer die einzige freie Variable in der durch f
codierten Formel erhaelt; 0, falls f keine Formel mit genau einer
freien Variablen codiert.
auch in der Arithmetik definierbar ist.
Dann definiert er folgende Formel:
G(x) = ~Ex y. Bew(y,subst(x,x))
bezeichnet dann mit g den Code dieser Formel (mit genau einer
freien Variablen!) und definiert den Goedelsatz
G(g).
Es gilt G(g) <=> ~ Ex y.Bew(y,subst(g,g)) <=> G(g) ist nicht beweisbar.
Letzteres deshalb, weil subst(g,g) gerade die Formel G(g) codiert.
Der Goedelsatz sagt also aus, dass er selbst nicht beweisbar
ist. Daraus folgt sofort, dass der Goedelsatz wahr ist, aber keinen
Beweis besitzt.
ENDE DER VORLESUNG.
Artikelaktionen