Martin Dietzfelbinger 30. Oktober 2009 · 2010. 5. 3. · Berechenbarkeit und Komplexit atstheorie...

Berechenbarkeit undKomplexitatstheorie

3. Vorlesung

Martin Dietzfelbinger

30. Oktober 2009

FG Komplexitatstheorie und Effiziente Algorithmen BuK – 30.10.2009

Turingmaschinen

• rechnen mit Zeichenreichen

• verallgemeinern DFAs und DPDAs

• verallgemeinern NFAs und NPDAs (”Nichtdeterminismus“)

• bilden ein extrem simples Maschinenmodell

(technisch vorteilhaft)

FG Komplexitatstheorie und Effiziente Algorithmen BuK – 30.10.2009 1

Turingmaschinen

Steuereinheit

B B B b a n d i n B B * # − s c h r i f t B B B B B B B ......

Bewegen um 1 BandfeldLese−Schreib−Kopf:

Schreiben Lesen

Übergangsfunktion

Zustandsmenge

gegenwärtiger Zustand

Turingmaschinen

Def.: Eine Turingmaschine M besteht aus sieben Komponen-

ten Q,Σ,Γ,B, q0,F , δ, wobei gilt:

(a) Q 6= ∅ ist endliche Menge. (Zustande.)

(b) Σ 6= ∅ ist endliche Menge. (Eingabealphabet.)

(c) Γ ist eine endliche Menge mit Σ ⊆ Γ. (Bandalphabet.)

B ∈ Γ− Σ. (Blanksymbol.)

(d) q0 ∈ Q. (Startzustand.)

(e) F ⊆ Q. (Akzeptierende Zustande.)

(f) δ : Q×Γ→ Q×Γ×{R,N,L}∪{−}. (Ubergangsfunktion.)

Turingmaschinen – Beispiel

TM M soll genau die Worter der Sprache

L = {anbncn | n ≥ 0}

akzeptieren.

Q = {A,C,D,E,H, Y }q0 = A

Σ = {a, b, c}Γ = {a, b, c, X, B}Blankbuchstabe B

Ubergangsfunktion δ als Tabelle:

q a b c X B

A (C, X, R) − − (A, X, R) (Y,B,N)C (C, a, R) (D, X, R) − (C, X, R) −D − (D, b, R) (E, X, R) (D, X, R) −E − − (E, c, R) − (H,B,L)H (H, a, L) (H, b, L) (H, c, L) (H, X, L) (A,B,R)Y − − − − −

”Sinn“ der Zustande:

A: Uberquere X-e, finde und streiche (”X“) erstes a.

Falls nur X-e gefunden: Check war erfolgreich.

C: Uberquere a-s und X-e, finde und streiche (”X“) erstes b.

D: Uberquere b-s und X-e, finde und streiche (”X“) erstes c.

E: Uberquere c-s, finde erstes B.

H: Fahre nach links, bis das erste B links des Eingabebereichs

erreicht ist.

Y: Akzeptierender Zustand, wird erreicht, wenn in Zustand A

nur X-e gelesen werden.

Turingmaschinen – graphische Darstellung

, RX|X

a|X , R , Rb|X

c|X , R

X|Xa|ab|b

, L, L, L, Lc|c

, Rc|cB | B, L

, Ra|a , Rb|b, RX|X , RX|X

B | B, N

B | B, R

Turingmaschinen – Beispiel Binaradditiona

q 00 01 10 11p0 (p, 0, R) (p, 1, R) (p, 1, R) (p, 2, R)p (p, 0, R) (p, 1, R) (p, 1, R) (p, 2, R)r0 − − − −r1 − − − −

s0, s1 − − − −

s0, s1 − − − −a

q 0 1 2 Bp0 − − − −p − − − (r0, B, L)r0 − − − −r1 − − − −

s0, s1 − − − −

s0, s1 − − − −a

q 0 1 2 Bp0 − − − −p − − − (r0, B, L)r0 − − − −r1 − − − −

s0, s1 − − − −Ablauf einer Berechnung:

B B (p0, 10) 11 00 01 11 B

B B 1 (p, 11) 00 01 11 B

B B 1 2 (p, 00) 01 11 B

B B 1 2 0 (p, 01) 11 B

B B 1 2 0 1 (p, 11) B

B B 1 2 0 1 2 (p,B)

B B 1 2 0 1 (r0, 2) B

B B 1 2 0 (r1, 1) 0 B

B B 1 2 (r1, 0) 0 0 B

B B 1 (r0, 2) 1 0 0 B

B B (r1, 1) 0 1 0 0 B

B (r1, B) 0 0 1 0 0 B

B (s1, 1) 0 0 1 0 0 B

Turingmaschinen

TMn definieren mathematisch exaktberechenbare Funktionen und entscheidbare Sprachen.

(Es gibt einen Algorithmus zur Berechnung von f bzw. (esgibt einen Algorithmuszur Entscheidung der Frage

”Ist x ∈ L?“)

Turingmaschinen

”Ist x ∈ L?“)

”Operationale Semantik“

Turingmaschinen

”Ist x ∈ L?“)

”Operationale Semantik“:

Drucke mit mathematischen Methoden aus, wie TMen rech-

nen, ohne auf die intuitiven Komponenten wie Bander,

Steuereinheiten, Zustande usw. Bezug zu nehmen.

Hier beispielhaft einmal vollstandig ausgefuhrt.

Turingmaschinen – Konfigurationen

”snapshot“

”Momentaufnahme“

”instantaneous description“

... B ...B B

r e s u l t a t i r r e l e vtnavelerri

Notiere nur: irrelevant(q, r)esultatBBirrelev

Komplette Beschreibung des Zustandes der TM.

Definition

Eine Konfiguration der TM M = (Q,Σ,Γ, B, q0, F, δ) ist

ein Wort

α1(q, a)α2

mit q ∈ Q, a ∈ Γ, α1, α2 ∈ Γ∗, wobei α1 nicht mit B beginnt

und α2 nicht mit B endet.

Definition

Eine Konfiguration der TM M = (Q,Σ,Γ, B, q0, F, δ) ist

ein Wort

α1(q, a)α2

mit q ∈ Q, a ∈ Γ, α1, α2 ∈ Γ∗, wobei α1 nicht mit B beginnt

und α2 nicht mit B endet.

KM : Menge aller Konfigurationen von M .

KM = (Γ∗ − {B}Γ∗)(Q× Γ)(Γ∗ − Γ∗{B})Abzahlbar (unendlich)!

Konfiguration k = α1(q, a)α2 sei gegeben.

Falls δ(q, a) = − : k Haltekonfiguration, kein Nachfolger.

Sonst: δ(q, a) = (q′, a′, D)

Bilde k = B α1(q, a)α2B = γ1c(q, a)dγ2, mit c, d ∈ Γ.

Sonst: δ(q, a) = (q′, a′, D)

k′ :=

γ1 (q′, c) a′ d γ2 , falls D = L;

γ1 c a′ (q′, d) γ2 , falls D = R;

γ1 c (q′, a′) d γ2 , falls D = N .

Sonst: δ(q, a) = (q′, a′, D)

k′ :=

γ1 (q′, c) a′ d γ2 , falls D = L;

γ1 c a′ (q′, d) γ2 , falls D = R;

γ1 c (q′, a′) d γ2 , falls D = N .

Entferne aus k′ alle B’s am Anfang und am Ende.

Sonst: δ(q, a) = (q′, a′, D)

k′ :=

γ1 (q′, c) a′ d γ2 , falls D = L;

γ1 c a′ (q′, d) γ2 , falls D = R;

γ1 c (q′, a′) d γ2 , falls D = N .

Liefert die Nachfolgekonfiguration k′ von k.

Sonst: δ(q, a) = (q′, a′, D)

k′ :=

γ1 (q′, c) a′ d γ2 , falls D = L;

γ1 c a′ (q′, d) γ2 , falls D = R;

γ1 c (q′, a′) d γ2 , falls D = N .

Liefert die Nachfolgekonfiguration k′ von k.

Schreibweise: k `M k′ bzw. k ` k′

Turingmaschinen – Beispiele

XXaX(C, b)bXcc ` XXaXX(D, b)Xcc und

XXaXXbX(D, c)c ` XXaXXbXX(E, c) , aber auch

cXcX(C, b) ` cXcXX(D,B).

Haltekonfiguration (nicht akzeptierend):

XaXb(D, a)c

Haltekonfiguration (nicht akzeptierend):

XaXb(D, a)c

Haltekonfiguration (akzeptierend):

XXX(Y,B)

TM - indirekte Nachfolgekonfigurationen

Definition

k `∗M k′ bzw. k `∗ k′:es existiert eine Folge

k = k0 `M k1 `M · · · `M ki = k′

Erlaubt: i = 0, d.h. k `∗ k gilt.

TM - indirekte Nachfolgekonfigurationen

Definition

k `∗M k′ bzw. k `∗ k′:es existiert eine Folge

k = k0 `M k1 `M · · · `M ki = k′

Erlaubt: i = 0, d.h. k `∗ k gilt.

”Reflexive und transitive Hulle“ von `M

Turingmaschinen – Startkonfiguration

. . . auf Eingabe x = a1 . . . an ∈ Σ∗:

Turingmaschinen – Startkonfiguration

. . . auf Eingabe x = a1 . . . an ∈ Σ∗:

init(x) := initM(x) :={

(q0, a1)a2 · · · an falls n ≥ 1(q0, B) falls n = 0

(Anfangs steht der Kopf unter dem ersten Eingabezeichen.)

Turingmaschinen – Berechnung

Gegeben: Turingmaschine M , x ∈ Σ∗.

Startkonfiguration k0 = init(x) bestimmt eindeutig eine

Konfigurationsfolge

k0 ` k1 ` k2 ` · · ·

(endlich oder unendlich):

Startkonfiguration k0 = init(x) bestimmt eindeutig eine

Konfigurationsfolge

k0 ` k1 ` k2 ` · · ·

(endlich oder unendlich):

die Berechnung von M auf x.

Turingmaschinen – 2 Moglichkeiten

(i) Die Berechnung von M auf x ist endlich, d.h. init(x) `∗ kfur eine (eindeutig bestimmte) Haltekonfiguration k.

Wir sagen: M auf x halt.

Wenn k akzeptierend: M akzeptiert x;

wenn k verwerfend: M verwirft x.

(ii) Die Berechnung von M auf x ist eine unendliche Folge von

Konfigurationen.

(ii) Die Berechnung von M auf x ist eine unendliche Folge von

Konfigurationen. Wir sagen: M auf x halt nicht.

Turingmaschinen – Akzeptierte Sprache

LM := {x ∈ Σ∗ |M akzeptiert x}

heißt die von M akzeptierte Sprache.

Turingmaschinen – Haltesprache

HM := {x ∈ Σ∗ |M halt auf x}

heißt die Haltesprache von M .

Σ∗ wird in drei disjunkte Teile zerlegt:

LM (X wird akzeptiert), HM − LM (x wird verworfen),

Σ∗ −HM (M halt nicht auf x).

Rekursiv aufzahlbare und rekursive SprachenDefinition

Eine Sprache L heißt rekursiv aufzahlbar (r. a.) (oder TM-akzeptierbar), falls es eine Turingmaschine M gibt, so dass

L = LM ist.

Definition

Eine Sprache L heißt rekursiv (rek.) (oder TM-entscheidbar), falls es eine Turingmaschine M gibt, die aufallen Inputs x ∈ Σ∗ halt, so dass L = LM ist.

L = LM ist.

Definition

Eine Sprache L heißt rekursiv (rek.) (oder TM-entscheidbar), falls es eine Turingmaschine M gibt, die aufallen Inputs x ∈ Σ∗ halt, so dass L = LM ist.

Klar: Jede rekursive Sprache ist r. a.

Haltesprachen = r.a. Sprachen

Bemerkung:

{LM |M TM} = {HM |M TM}.

Bemerkung:

Die Haltesprachen sind identisch mit den r.a. Sprachen.

Bemerkung:

Beweis:

”⊆“:

Bemerkung:

Beweis:

”⊆“: Aus TM M baue TM M ′ mit HM ′ = LM .

Bemerkung:

Beweis:

(M ′ rechnet wie M . Wenn M mit δ(q, a) = − halt und q ∈ Q − F ist,

lasse M ′ mit δ′(q, a) = (q, a,N) in eine”Endlosschleife“ gehen.)

Bemerkung:

Beweis:

”⊇“:

Bemerkung:

Beweis:

”⊇“: Aus TM M baue TM M ′ mit LM ′ = HM .

Bemerkung:

Beweis:

”⊇“: Aus TM M baue TM M ′ mit LM ′ = HM .

(Andere F in F ′ = Q um.)

Turingmaschinen – Ausgabe

Ausgabe fM(x) von M auf x:

Falls M auf x nicht halt, ist fM(x) undefiniert.

Sonst sei k die (eindeutige) Haltekonfiguration mit

init(x) `∗M k, und k = α1(q, b)α2, α1, α2 ∈ Γ∗, b ∈ Γ, q ∈ Q.

Dann ist fM(x) das langste Prafix von bα2, das den Blank-

buchstaben B nicht enthalt.

Dann ist fM(x) das langste Prafix von bα2, das den Blank-

buchstaben B nicht enthalt.

Beachte: Fur die Bestimmung der Ausgabe von M auf x ist

es unerheblich, ob M x akzeptiert oder verwirft.

Partiell rekursive Funktionen

Definition

Eine Funktion f : D → R heißt partiell rekursiv, falls es

eine TM M = (Q,Σ,Γ, . . .) gibt derart dass D = HM ,

R ⊆ (Γ− {B})∗ und f = fM ist.

Definition

Eine Funktion f : Σ∗ → R heißt rekursiv oder deutlicher

total rekursiv, falls es eine TM M = (Q,Σ,Γ, . . .) gibt

derart dass f = fM ist.

Definition

Eine Funktion f : Σ∗ → R heißt rekursiv oder deutlicher

total rekursiv, falls es eine TM M = (Q,Σ,Γ, . . .) gibt

derart dass f = fM ist.

Beachte: Diese TM M halt auf allen Inputs x ∈ Σ∗.

Wozu Turingmaschinen?

• Mathematische Untersuchungen, Vergleich mit anderen Mo-

dellen, Aquivalenz zu Stufen der Chomsky-Hierarchie,”uni-

verselle“ (programmierbare) TM, Konstruktion nichtrekur-

siver Sprachen

Primitive Struktur des Modells gunstig.

siver Sprachen

• Nachweis fuhren, dass f (partiell) rekursiv, dass L rekursiv.

D.h.: TM programmieren!

siver Sprachen

• Nachweis fuhren, dass f (partiell) rekursiv, dass L rekursiv.

D.h.: TM programmieren!

Primitive Struktur des Modells sehr ungunstig.

Beachte: In der Gestaltung der Komponenten Γ, Q, δ sind

wir frei.

Wahle diese Komponenten moglichst gunstig und

strukturiert.

Beachte: In der Gestaltung der Komponenten Γ, Q, δ sind

wir frei.

Wahle diese Komponenten moglichst gunstig und

strukturiert.

Gravierende Programmierfehler:

• Unbegrenzt viele Bandbuchstaben;

• Unbegrenzt viele Zustande in der Steuereinheit;”Register“

in der Steuereinheit, das beliebige Zahlen speichert

Turingmaschinen mussen Zahlen in Ziffernschreibweise auf

das Band schreiben!

1.2 Programmiertechniken

. . . und”Robustheit des TM-Modells“ gegenuber Varianten.

Endlicher Speicher in der Steuereinheit (1.2.1)

Beispiel :

L = {a1a2 · · · an−1an ∈ Σ∗ | n ≥ 2, a1a2 = an−1an}

Sprache der Worter, bei denen die beiden Anfangsbuchstaben

gleich den beiden Endbuchstaben sind.

Endlicher Speicher in der Steuereinheit (1.2.1)

Beispiel :

L = {a1a2 · · · an−1an ∈ Σ∗ | n ≥ 2, a1a2 = an−1an}

Sprache der Worter, bei denen die beiden Anfangsbuchstaben

gleich den beiden Endbuchstaben sind.

Programmieridee: Speichere a1 und a2 in einem Register in

der Steuereinheit.

Endlicher Speicher in der Steuereinheit

δ(q0, a) = ((q1, a), a, R), fur a ∈ Σ

δ((q1, a), b) = ((q2, a, b), b, R), fur a, b ∈ Σ

δ(q0, a) = ((q1, a), a, R), fur a ∈ Σ

δ((q2, a, b), c) = ((q2, a, b), c, R), fur a, b, c ∈ Σ

δ(q0, a) = ((q1, a), a, R), fur a ∈ Σ

δ((q2, a, b), B) = ((q3, a, b), B, L), fur a, b, c ∈ Σ

δ(q0, a) = ((q1, a), a, R), fur a ∈ Σ

δ((q3, a, b), b) = ((q4, a), b, L), fur a, b ∈ Σ

δ(q0, a) = ((q1, a), a, R), fur a ∈ Σ

δ((q4, a), a) = (q5, a,N), fur a ∈ Σ

δ(q0, a) = ((q1, a), a, R), fur a ∈ Σ

δ((q4, a), a) = (q5, a,N), fur a ∈ Σ

Zustandsmenge: Q :={q0, q5} ∪ {(q1, a), (q4, a) | a ∈ Σ} ∪ {(q2, a, b), (q3, a, b) | a, b ∈ Σ}

δ(q0, a) = ((q1, a), a, R), fur a ∈ Σ

δ((q4, a), a) = (q5, a,N), fur a ∈ Σ

Zustandsmenge: Q :={q0, q5} ∪ {(q1, a), (q4, a) | a ∈ Σ} ∪ {(q2, a, b), (q3, a, b) | a, b ∈ Σ}Analog kann man bereitstellen: Flagbits, Register aus Flagbits.

Spurtechnik (1.2.2)

∆ Alphabet, k ≥ 1.

Vorstellung: Band hat k Spuren (jede Zelle ist eine Spalte)

Spurtechnik (1.2.2)

Spur 12345

e i n s BB z w e i3 3 3 3 Bv i e r 4B B B B 5

Spurtechnik (1.2.2)

Spur 12345

e i n s BB z w e i3 3 3 3 Bv i e r 4B B B B 5

Programmierfehler: k nicht begrenzt.

Spurtechnik

Hierzu:

Γ ⊇ ∆k =

: a1, . . . , ak ∈ ∆

Spurtechnik

Hierzu:

Γ ⊇ ∆k =

: a1, . . . , ak ∈ ∆

Verschiedene Spuranzahlen ≤ k in verschiedenen Bandab-

schnitten – oder gemischt:

∆ ∪∆2 ∪ · · · ∪∆k ⊆ Γ.

Spurtechnik

Hierzu:

Γ ⊇ ∆k =

: a1, . . . , ak ∈ ∆

Verschiedene Spuranzahlen ≤ k in verschiedenen Bandab-

schnitten – oder gemischt:

∆ ∪∆2 ∪ · · · ∪∆k ⊆ Γ.

Programmierfehler: Spuranzahl nicht begrenzt.

Spurtechnik

Markierungen auf Spur 2:

.........

B b a n d # # i n s c h r i f t* +* +

TextspurMarkierung

Spurtechnik

Markierungen auf Spur 2:

.........

B b a n d # # i n s c h r i f t* +* +

TextspurMarkierung

Programmierfehler:

unbeschrankt viele Markierungen in einer Zelle.

Technik: Bandinhalt verschieben (1.2.3)

vorher:

Spur 1

Spur 2

nachher:

Spur 1

Spur 2

Hilfsspur

l i n k s r e c h t s u n d s o w e i t e r

l i n k s B B B B B B B B r e c h t s u n d s o w

r e c h t s u n d s o w

zu verschieben

Technik: Bandinhalt verschieben (1.2.3)

vorher:

Spur 1

Spur 2

nachher:

Spur 1

Spur 2

Hilfsspur

l i n k s r e c h t s u n d s o w e i t e r

l i n k s B B B B B B B B r e c h t s u n d s o w

r e c h t s u n d s o w

zu verschieben

Zweck: Erzeugen von Platz im Inneren einer Bandinschrift.

Bandinhalt verschieben

”Detaillierte Beschreibung“, kein TM-Programm:

Kopf nach rechts bis zum /c.

Wiederhole folgendes (1.–5.):

1. Speichere Buchstaben a aus Spur 1 in Steuereinheit;

markiere Zelle mit +;

2. Fahre Kopf nach rechts bis zum ersten B auf der

Hilfsspur jenseits vom �;uberschreibe dieses B mit dem gespeicherten a;

3. Fahre Kopf nach links, bis + erreicht wird;

losche dieses +;

3. Fahre Kopf nach links, bis + erreicht wird;

losche dieses +;

4. Wenn Kopf in der $-Zelle steht, gehe zu 6.

5. Sonst Kopf um eine Zelle nach rechts und zu 1.

6. Fahre Kopf nach links bis zur /c-Zelle;

7. Fahre Kopf nach rechts bis zur �-Zelle, uberschreibe dabei

Spur 1 mit B;

8. von der �-Zelle (einschließlich) nach rechts gehend kopiere

die Buchstaben von Spur 3 auf dasselbe Feld in Spur 1,

Spur 1 mit B;

die Buchstaben von Spur 3 auf dasselbe Feld in Spur 1, losche

dabei gleichzeitig Spur 3, bis zur ersten Zelle (ausschließlich),

die in Spur 3 ein B enthalt;

Spur 1 mit B;

9. fahre den Kopf nach links bis zur /c-Zelle.

Spur 1 mit B;

Ubung: ein TM-Programm erstellen.

Spur 1 mit B;

Wieviele Schritte?

Spur 1 mit B;

Wieviele Schritte? O(l · d), l: Lange, d: Distanz.

Modelleinschrankung: Einseitigunbeschranktes Band (1.2.4)

Idee: Wenn man eine Rechnung auf einem gewohnlichen Band

durchfuhren kann, dann auch auf einem Band, bei dem

niemals eine Zelle links der Eingabe betreten wird

Modelleinschrankung: Einseitigunbeschranktes Band (1.2.4)

Idee: Wenn man eine Rechnung auf einem gewohnlichen Band

durchfuhren kann, dann auch auf einem Band, bei dem

niemals eine Zelle links der Eingabe betreten wird

verboten

i n p u t B B B B B B B ...

0 1 2 3 4 5

Einseitig unbeschranktes Band

Formal:

• Zu jeder beliebigen TM M gibt es eine TM M ′ mit LM =LM ′ und HM = HM ′ und fM = fM ′ derart dass der

Bandkopf von M ′ niemals eine Bandzelle links von seiner

anfanglichen Position besucht.

Formal:

Die Behauptung wird konstruktiv bewiesen:

Formal:

Gegeben M , kann man M zu einem geeigneten M ′ umbauen.

Formal:

Gegeben M , kann man M zu einem geeigneten M ′ umbauen.

Achte auf solche Konstruktionen! Wesentliche Technik!

Idee: Linke Seite des Bandes umklappen.

b a n d + v o n + M + 2 s e i t i g B ...

−3 −2 −1 0 1 2 3 4 5

von M’:n + M + 2 s e i t i g B B B B B B

* o v + d n a b B B B B B B B B B

−1 −2 −3

0 1 2 3 4

Steuereinheit der neuen TM M ′:

Steuer−

einheit

von M oben

ea Puffer

oben/unten?

Formal:

Formal: M ′ = (Q′,Σ,Γ′, B′, q′0, F′, δ′) mit

Q′ = Q× {u, o} ∪ {q′0};

Q′ = Q× {u, o} ∪ {q′0};Γ′ = Γ× (Γ ∪ {∗}) ∪ Σ;

B′ = (B,B)

Neue Ubergangsfkt. (a, b, c ∈ Γ, q, p ∈ Q,D ∈ {L,R,N}):