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

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

Qδ

q

qm q

q

0

1

2

3q

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

q


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:

a

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

Start

C D

HY

A

E

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

q

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)




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 .







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.




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




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




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






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 ∈ Σ



δ(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)


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

: a1, . . . , ak ∈ ∆

.


Spurtechnik

Hierzu:

Γ ⊇ ∆k =

a1

...ak

: a1, . . . , ak ∈ ∆

.

Verschiedene Spuranzahlen ≤ k in verschiedenen Bandab-

schnitten – oder gemischt:

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


Spurtechnik

Hierzu:

Γ ⊇ ∆k =

a1

...ak

: 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

c $

B B B

c $

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

c $

B B B

c $

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;




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

q0


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.



Idee: Linke Seite des Bandes umklappen.

5

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

Band

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};Γ′ = Γ× (Γ ∪ {∗}) ∪ Σ;




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

B′ = (B,B)


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



δ′(q′0, a) = ((q0, o), (a, ∗), N), fur a ∈ Σ;



δ′(q′0, a) = ((q0, o), (a, ∗), N), fur a ∈ Σ;

δ′(q′0, (B,B)) = ((q0, o), (B, ∗), N), (falls der Input ε ist);



δ′(q′0, a) = ((q0, o), (a, ∗), N), fur a ∈ Σ;


δ′((q, o), (a, c)) = ((p, o), (b, c), D), fur q ∈ Q, δ(q, a) = (p, b,D), c 6= ∗;



δ′(q′0, a) = ((q0, o), (a, ∗), N), fur a ∈ Σ;



δ′((q, u), (c, a)) = ((p, u), (c, b), D), fur q ∈ Q, δ(q, a) = (p, b,D), a 6= ∗,



δ′(q′0, a) = ((q0, o), (a, ∗), N), fur a ∈ Σ;




wobei R = L, L = R, N = N ;



δ′(q′0, a) = ((q0, o), (a, ∗), N), fur a ∈ Σ;





δ′((q, u), (a, ∗))δ′((q, o), (a, ∗))

}=



δ′(q′0, a) = ((q0, o), (a, ∗), N), fur a ∈ Σ;





δ′((q, u), (a, ∗))δ′((q, o), (a, ∗))

}=

((p, u), (b, ∗), R), falls D = L,

((p, o), (b, ∗), R), falls D = R,

((p, o), (b, ∗), N), falls D = N ;



δ′(q′0, a) = ((q0, o), (a, ∗), N), fur a ∈ Σ;





δ′((q, u), (a, ∗))δ′((q, o), (a, ∗))

}=

((p, u), (b, ∗), R), falls D = L,

((p, o), (b, ∗), R), falls D = R,

((p, o), (b, ∗), N), falls D = N ;

wobei immer δ(q, a) = (p, b,D).



Nach dem Halten:

Transport des Ausgabewortes in Spur 1, beginnend in der

∗-Zelle,

abschließen mit (B,B).

Hierfur muss man weitere Zustande einfuhren und δ′ erweitern.


Bis nachste Woche

• Skript Seiten 25–45 (Beispiel 1.1.19 optional)

• Ubungsaufgaben drucken und vorbereiten


Documents

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