Kapitel 20: Turingmaschinen Thomas Worschgbi.ira.uka.de/vorlesungen/k-20-turingmaschinen-folien.pdf · Grundbegri˙e der Informatik Kapitel 20: Turingmaschinen Thomas Worsch KIT,

Grundbegri�e der Informatik

Kapitel 20: Turingmaschinen

Thomas Worsch

KIT, Institut für Theoretische Informatik

Wintersemester 2015/2016

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 1 / 73

Überblick

Eine technische Vorbemerkung

Turingmaschinen

Berechnungskomplexität

Unentscheidbare Probleme


Wo sind wir?


Turingmaschinen




Erinnerung: partielle Funktionen von A nach B

A

B

rechtseindeutige Relation f ⊆ A × B

für jedes a gibt es höchstens ein b ∈ B mit (a,b) ∈ f

totale Funktionen sind Spezialfall

ggf. wieder b = f (a) geschrieben

andernfalls ist „f (a) undefiniert“

Notation f : A d B


Wo sind wir?


Turingmaschinen




Turingmaschinen: Ursprung

eingeführt von Alan Turing (1912 – 1954)

http://www.turing.org.uk/turing/index.html

„On computable numbers, with an application to theEntscheidungsproblem“Proceedings of the London Mathematical Society 42, 1936,

S. 230–265.

„The informal arguments [. . . ] are as lucid and convincing nowas they were then. [. . . ] the best introduction to the subject[. . . ] superior piece of expository writing.“http://www.scholarpedia.org/article/Turing_machine


http://www.turing.org.uk/turing/index.html

http://www.scholarpedia.org/article/Turing_machine

Eine Turingmaschine im Bild

z

· · · 2 2 a b b a a 2 · · ·



z

· · · 2 2 a b b a a 2 · · ·

Steuereinheit: endliche Zustandsmenge Z



z

· · · 2 2 a b b a a 2 · · ·

endliche Zustandsmenge Z

Band, in Felder unterteilt:

beschri�et mit Symbolen aus Bandalphabet X



z

· · · 2 2 a b b a a 2 · · ·


Bandalphabet X

nächste Aktion festgelegt durch

aktuellen Zustand z und

aktuell gelesenes Symbol x



z

· · · 2 2 a b b a a 2 · · ·


Bandalphabet X

Schri�

neue Feldbeschri�ung д(z,a)neuer Zustand f (z,a)Kopfbewegungm(z,a)



z ′

· · · 2 2 c b b a a 2 · · ·


Bandalphabet X

Schri�:

neue Feldbeschri�ung д(z,a) = cneuer Zustand f (z,a) = z ′

Kopfbewegungm(z,a) = +1


Turingmaschine formalisiert als T = (Z , z0,X , f , д,m)

Zustandsmenge Z

Anfangszustand z0 ∈ Z

Bandalphabet X

meist mit Blanksymbol 2

partielle Zustandsüberführungsfunktion

f : Z × X d Z

partielle Ausgabefunktion

д : Z × X d X und

partielle Bewegungsfunktion

m : Z × X d {−1, 0, 1} oder {L, 0,R}

f , д,m mit gleichem Definitionsbereich


Turingmaschinen: graphische Darstellung (TM BB3)

A

H

B

C

2 |1R

1 |1R

2 |2R

1 |1R

2 |1L

1 |1L


Turingmaschinen: graphische Darstellung

A

B

C

2 |1R

2 |2R

1 |1R

2 |1L

1 |1L


Turingmaschinen: tabellarische Darstellung

A

B

C

2 |1R

2 |2R

1 |1R

2 |1L

1 |1L

so:

A B C

2 1,R,B 2,R,C 1,L,C1 1,R,B 1,L,A

oder so:

A B C

2 B,1,R C,2,R C,1,L1 B,1,R A,1,L

oder . . .


Beispielberechnung (1)

A B C H

2 1,R,B 2,R,C 1,L,C1 1,R,H 1,R,B 1,L,A

A2 2 2 2 2 2 2 2



A B C H

2 1,R,B 2,R,C 1,L,C1 1,R,H 1,R,B 1,L,A

A2 2 2 2 2 2 2 2



A B C H

2 1,R,B 2,R,C 1,L,C1 1,R,H 1,R,B 1,L,A

A2 2 2 2 2 2 2 2



A B C H

2 1,R,B 2,R,C 1,L,C1 1,R,H 1,R,B 1,L,A

A2 2 2 2 2 2 2 2



A B C H

2 1,R,B 2,R,C 1,L,C1 1,R,H 1,R,B 1,L,A

A2 2 2 2 2 2 2 2

B2 2 2 1 2 2 2 2



A B C H

2 1,R,B 2,R,C 1,L,C1 1,R,H 1,R,B 1,L,A

A2 2 2 2 2 2 2 2

B2 2 2 1 2 2 2 2



A B C H

2 1,R,B 2,R,C 1,L,C1 1,R,H 1,R,B 1,L,A

A2 2 2 2 2 2 2 2

B2 2 2 1 2 2 2 2



A B C H

2 1,R,B 2,R,C 1,L,C1 1,R,H 1,R,B 1,L,A

A2 2 2 2 2 2 2 2

B2 2 2 1 2 2 2 2

C2 2 2 1 2 2 2 2


Turingmaschinen: Konfigurationen

Konfiguration: „Gesamtzustand“ einer Turingmaschine

c = (z,b,p) ∈ Z × XZ × Zaktueller Zustand z ∈ Z der Steuereinheit,

aktuelle Beschri�ung des gesamten Bandes:

totale Abbildung b : Z→ Xaktuelle Position p ∈ Z des Kopfes

CT : Menge aller Konfigurationen von T


Turingmaschinen: «überschaubare» Bandbeschri�ungen

Bandbeschri�ung: ein «potenziell unendliches Gebilde»

In weiten Teilen der Informatik interessieren

endliche Berechnungen, die

aus endlichen Eingaben

endliche Ausgaben

berechnen.

«Fast» das ganze Band ist immer «leer»:

Bandalphabet enthält Blanksymbol 2 ∈ XBandbeschri�ungen: immer nur endlich viele Felder , 2


Ein Schri� einer Turingmaschine

c = (z,b,p) aktuelle Konfiguration einer TM T

wenn für (z,b (p)) die Funktionen f , д undm definiert,

dann kann die TM einen Schri� machen

Nachfolgekonfiguration c ′ = (z ′,b ′,p ′):

z ′ = f (z,b (p))

∀i ∈ Z : b ′(i ) =

b (i ) falls i , p

д(z,b (p)) falls i = p

p ′ = p +m(z,b (p))

schreiben c ′ = ∆1 (c ), also

∆1 : CT d CT


Längere Beispielberechnung von BB3

A2 2 2 2 2 2 2 2

B2 2 2 1 2 2 2 2

C2 2 2 1 2 2 2 2

C2 2 2 1 2 1 2 2

C2 2 2 1 1 1 2 2

A2 2 2 1 1 1 2 2

B2 2 1 1 1 1 2 2

B2 2 1 1 1 1 2 2

B2 2 1 1 1 1 2 2

B2 2 1 1 1 1 2 2

B2 2 1 1 1 1 2 2

C2 2 1 1 1 1 2 2

C2 2 1 1 1 1 2 1

C2 2 1 1 1 1 1 1

A2 2 1 1 1 1 1 1

H2 2 1 1 1 1 1 1


Berechnungen und Endkonfigurationen

c ist Endkonfiguration, falls ∆1 (c ) nicht definiert ist.

endliche Berechnung: (c0, c1, c2, . . . , ct )

wobei für alle 0 < i ≤ t gilt ci = ∆1 (ci−1)

haltende Berechnung: endliche Berechnung,

deren letzte Konfiguration eine Endkonfiguration ist

unendliche Berechnung (nicht haltend):

unendliche Folge (c0, c1, c2, . . . ) mit ∀i > 0 : ci = ∆1 (ci−1)simples Beispiel

f (z,x ) = z,

д(z,x ) = x und

m(z,x ) = 1Kann man so etwas «wegkonstruieren» ?


Rechnen bis zur Endkonfiguration

für t ∈ N0 Abbildung ∆t : CT d CT

∆0 = I

∆t+1 = ∆1 ◦ ∆t

von jedem c gibt es genau eine maximal lange Berechnung

Haltezeitpunkt gegebenenfalls eindeutig

∆∗ : CT d CT mit

∆∗ (c ) =

∆t (c ) falls ∆t (c ) definiert und

Endkonfiguration

undefiniert falls ∆t (c ) für alle t ∈ N0 definiert


zwei Arten von Turingmaschinen

Berechung von Funktionen

Erkennung formaler Sprachen

Turingmaschinenakzeptoren

Entscheidungsprobleme


Eingaben und Anfangskonfigurationen

Eingabealphabet A ⊂ X r {2}

Blanksymbol nicht dabei

Anfangskonfiguration c0 (w ) = (z,b,p) für Eingabe w ∈ A∗

z = z0b = bw : Z→ X

bw (i ) =

2 falls i < 0 ∨ i ≥ |w |w (i ) falls 0 ≤ i ∧ i < |w |

p = 0

Anfangskonfiguration bei Eingabe mehrerer Argumente

geeignet harmlos

z. B. 222[1011][101]22 oder . . .


Ergebnisse von Turingmaschinenberechnungen

Berechung von Funktionen

ein Ausgabewort

auf dem ansonsten leeren Band

Erkennung formaler Sprachen: ein Bit akzeptiert/abgelehnt

Turingmaschinenakzeptor T :

Teilmenge F ⊂ Z akzeptierender Zustände

T akzeptiert w , wenn

T für Eingabe w hält und

Zustand der Endkonfiguration ∆∗ (c0 (w )) akzeptierend

L(T ): Menge der akzeptierten Wörter

die von der Turingmaschine akzeptierte Sprache


Beispiel: Palindromerkennung

ein Palindrom ist ein Wort, das seinem Spiegelbild gleicht

also von hinten und von vorne gelesen «gleich»

bei dem also

erstes und letztes Symbol übereinstimmen

zweites und vorletztes Symbol übereinstimmen

usw.

bei dem also


und dazwischen ein Palindrom steht


Beispiel: Palindromerkennung

ein Palindrom ist ein Wort, das seinem Spiegelbild gleicht

also von hinten und von vorne gelesen «gleich»

bei dem also


zweites und vorletztes Symbol übereinstimmen

usw.

bei dem also


und dazwischen ein Palindrom steht


Palindromerkennung: Beispielberechnung

r2 2 a b b a 2

ra2 2 2 b b a 2

ra2 2 2 b b a 2

ra2 2 2 b b a 2

ra2 2 2 b b a 2

la2 2 2 b b a 2

l2 2 2 b b 2 2

l2 2 2 b b 2 2

l2 2 2 b b 2 2

r2 2 2 b b 2 2

rb2 2 2 2 b 2 2

rb2 2 2 2 b 2 2

lb2 2 2 2 b 2 2

l2 2 2 2 2 2 2

r2 2 2 2 2 2 2

f+2 2 2 2 2 2 2


Palindromerkennung: Beispielberechnung

r2 2 a b b a 2

ra2 2 2 b b a 2

ra2 2 2 b b a 2

ra2 2 2 b b a 2

ra2 2 2 b b a 2

la2 2 2 b b a 2

l2 2 2 b b 2 2

l2 2 2 b b 2 2

l2 2 2 b b 2 2

r2 2 2 b b 2 2

rb2 2 2 2 b 2 2

rb2 2 2 2 b 2 2

lb2 2 2 2 b 2 2

l2 2 2 2 2 2 2

r2 2 2 2 2 2 2

f+2 2 2 2 2 2 2


Palindromerkennung: Beispielturingmaschine

ra la

r f+ f− l

rb lb

a |2R

b |2R

2 |2R

a |aR, b |bR

2 |2L

a |aR, b |bR

2 |2L

a |2L

b |2L2 |20

a |2L

b |2L2 |20

a |aL, b |bL

2 |2R


Palindromerkennung: Beispielturingmaschine

ra la

r f+ l

rb lb

a |2R

b |2R

2 |2R

a |aR, b |bR

2 |2L

a |aR, b |bR

2 |2L

a |2L

2 |20

b |2L2 |20

a |aL, b |bL

2 |2R


Aufzählbare und entscheidbare Sprachen

zwei Möglichkeiten, wenn w von T nicht akzeptiert wird:

1. T hält für Eingabe w , aber letzter Zustand nicht akzeptierend

2. T hält für Eingabe w nicht

Was weiß man?

1. T ist fertig, Eingabe abgelehnt

2. T ist noch nicht fertig.

Ob T irgendwann w noch akzeptiert oder ablehnt, ist unklar.

man unterscheide

1. L heißt entscheidbare Sprache, wenn es eine Turingmaschine

gibt, die immer hält und L akzeptiert.

2. L heißt aufzählbare Sprache, wenn es eine Turingmaschine

gibt, die L akzeptiert.

Entscheidbarkeit ist eine stärkere Forderung


Was ist wichtig

Das sollten Sie mitnehmen:

Turingmaschinen

Steuereinheit endlich

Band unendlich, aber

nur endlich viel «nicht leer»

alles endlich beschreibbar

klassische Formalisierung von «Algorithmus»

Berechnungen

haltende

nicht haltende

Das sollten Sie üben:

Beispielturingmaschinen konstruieren

Beispielturingmaschinen verstehen


Wo sind wir?


Turingmaschinen




Achtung Achtung Achtung Achtung Achtung Achtung

Annahme in diesem Abschni�:

Turingmaschinen halten für jede Eingabe.

Aber nur in diesem Abschni�!

Versprechen: Für die Fragestellungen in diesem Abschni�

(Komplexitätstheorie) ist das in Ordnung

Vorsicht: Für die Fragestellungen im Abschni� über

unentscheidbare Probleme ist das nicht mehr in Ordnung.



Annahme in diesem Abschni�:

Turingmaschinen halten für jede Eingabe.

Aber nur in diesem Abschni�!

Versprechen: Für die Fragestellungen in diesem Abschni�

(Komplexitätstheorie) ist das in Ordnung

Vorsicht: Für die Fragestellungen im Abschni� über

unentscheidbare Probleme ist das nicht mehr in Ordnung.


Zeitkomplexität — der Rechenzeitbedarf einer TM

definiere

timeT : A+ → N+TimeT : N+ → N+

wie folgt:

timeT (w ) = das t , für das ∆t (c0 (w )) Endkonfiguration

TimeT (n) = max{timeT (w ) | w ∈ An }

TimeT heißt Zeitkomplexität der Turingmaschine

«max» =̂ «worst case»

Zeitkomplexität von T polynomiell,

wenn TimeT (n) ∈ O (p (n)) für ein Polynom p (n)


Zeitkomplexität der TM für Palindromerkennung

Für Eingabe der Länge n ≥ 2 schlimmstenfalls

1. erstes und letztes Symbol miteinander vergleichen,

und weil übereinstimmend, zurücklaufen und dann

2. für Teilwort der Länge n − 2 ohne Randsymbole

wieder ein Palindromtest

für n ≥ 2: Time(n) ≤ 2n + 1 + Time(n − 2)

für Wörter der Längen 1 und 2 Zeitaufwand konstant

Time(n) ∈ O(n2), d. h. polynomielle Zeitkomplexität


Platzkomplexität oder Raumkomplexität einer TM

definiere

spaceT (w ) : A+ → N+SpaceT (n) : N+ → N+

wie folgt

spaceT (w ) = Anzahl Felder, die während der

Berechnung für Eingabe w benötigt

SpaceT (n) = max{spaceT (w ) | w ∈ An }

Feld «benötigt», wenn

anfangs dort Eingabesymbol oder

Feld mindestens einmal vom TM-Kopf besucht


Raumkomplexität der TM für Palindromerkennung

benötigte Felder:

n Felder mit den Eingabesymbolen

ein weiteres Feld rechts davon

polynomieller, nämlich linearer, Platzbedarf

Space(n) = n + 1 ∈ Θ (n)


Zeitkomplexität versus Raumkomplexität (1)

Wenn T für Eingabe w genau time(w ) Schri�e macht,

dann kann T höchstens 1 + time(w ) Felder besuchen.

folglich immer

space(w ) ≤ |w | + time(w )

Jede Turingmaschine mit polynomieller Laufzeit hat auch

nur polynomiellen Platzbedarf.


Zeitkomplexität versus Raumkomplexität (2)

nun umgekehrt von Raum- zu Zeitkomplexität

Auf k Feldern können ( |X | − 1)k „interessante“

verschiedene Inschri�en stehen.

Es gibt Turingmaschinen mit

polynomieller Raumkomplexität aber

exponentieller Zeitkomplexität.


Eine Komplexitätsklasse ist eine Menge von Problemen

hier nur formale Sprachen (Entscheidungsprobleme)

Festlegung o� durch Beschränkung der zur Verfügung

stehen Ressourcen, also z. B. Schranken für Zeitkomplexität

oder Raumkomplexität (oder beides)

Beispiel: alle formalen Sprachen, die von Turingmaschinen

entschieden werden können, bei denen gleichzeitig

Zeitkomplexität in O(n3)

und

Raumkomplexität in O(n3/2 logn

)ist

wobei n die Länge des Eingabewortes ist.


P und PSPACE — zwei wichtige Komplexitätsklassen

PMenge aller formaler Sprachen, die von TM entschieden

werden können, deren Zeitkomplexität polynomiell ist.

PSPACEMenge aller formaler Sprachen, die von TM entschieden

werden können, deren Raumkomplexität polynomiell ist.

Beispiele

«Palindrome» ist in P«Äquivalenz regulärer Ausdrücke» ist in PSPACE


Beziehung zwischen P und PSPACE — unklar

polynomielle Laufzeit =⇒ polynomieller Platzbedarf:

P ⊆ PSPACE

Und umgekehrt? Vorsicht!

TM mit polynomiellem Platzbedarf kann

exponentiell viele Schri�e machen kann.

Solche Turingmaschinen gibt es.

Aber!

trotzdem könnte PSPACE ⊆ P sein,

wenn immer viel schnellere äquivalente TM existiert

Bei P und PSPACE geht es um formale Sprachen,

nicht um Turingmaschinen.

großes o�enes Problem:

P = PSPACE oder P , PSPACE ?




P ⊆ PSPACE





Aber!










P ⊆ PSPACE





Aber!










P ⊆ PSPACE





Aber!










P ⊆ PSPACE





Aber!










P ⊆ PSPACE





Aber!








Was ist wichtig


Zeitkomplexität und Raumkomplexität

in Abhängigkeit von Eingabegröße der schlimmste Fall

evtl. nur obere Schranke

Komplexitätsklassen

durch Beschränkung der zur Verfügung stehen Ressourcen, also

z. B. Schranken für Zeitkomplexität oder/und Raumkomplexität

wichtig: P und PSPACE


Abschätzung der Zeit- und Raumkomplexität von TM


Wo sind wir?


Turingmaschinen





Ab sofort ist es wieder von Bedeutung, dass

Turingmaschinen in «Endlosschleifen» laufen können.


Codierungen von Turingmaschinen

Ziel: beschreibe jede Turingmaschine durch ein Wort

im folgenden beispielha� eine Möglichkeit, das zu tun

für Beschreibungen Alphabet A = {[,],0,1}es reicht aber auch A = {0,1}oder sogar A = {1}

sogenannte Gödelisierung nach Kurt Gödel (1906-1978)

wesentliche Arbeit:

Kurt Gödel (1931): Über formal unentscheidbare Sätze derPrincipia Mathematica und verwandter Systeme I,Monatshe�e für Mathematik und Physik, 38, S. 173-198.

www.springerlink.com/content/p03501kn35215860/



Codierungen von Turingmaschinen

Ziel: beschreibe jede Turingmaschine durch ein Wort

im folgenden beispielha� eine Möglichkeit, das zu tun

für Beschreibungen Alphabet A = {[,],0,1}es reicht aber auch A = {0,1}oder sogar A = {1}

sogenannte Gödelisierung nach Kurt Gödel (1906-1978)

wesentliche Arbeit:

Kurt Gödel (1931): Über formal unentscheidbare Sätze derPrincipia Mathematica und verwandter Systeme I,Monatshe�e für Mathematik und Physik, 38, S. 173-198.




Beispielcodierung (1) — Zustände

Turingmaschine T = (Z , z0,X ,2, f ,д,m)

Codierung der Zustände:

Zustände ab 0 durchnummeriert.

Anfangszustand Nummer 0.

Repräsentation der Zustände durch

gleich lange Binärdarstellungen der Nummern in [ ]schreibe codZ (z) für Codierung von Zustand zBeispiele:

codZ (z0) = [0000]codZ (z1) = [0001]. . .


Beispielcodierung (2) — Symbole


Codierung der Symbole:

Bandsymbole ab 0 durchnummeriert.

Blanksymbol bekommt Nummer 0.

Repräsentation der Bandsymbole durch

gleich lange Binärdarstellungen der Nummern in [ ]schreibe codX (x ) für Codierung von Bandsymbol xBeispiele:

codX (2) = [0000]codX (a) = [0001]. . .


Beispielcodierung (3) — Kopfbewegungen


Codierung der Kopfbewegungen

[10], [00] und [01] für −1, 0, +1 resp.

schreibe codM (r ) für Codierung der Bewegungsrichtung r .

also

codM (−1) = [10]codM (0) = [00]codM (+1) = [01]


Beispielcodierung (4) — einzelne Funktionswerte


Codierung einzelner Funktionswerte von f , д undm

wenn für Argumentpaar (z,x ) nicht definiert, Codierung

codfgm (z,x ) = [ codZ (z) codX (x )[][][]].

wenn für Argumentpaar (z,x ) definiert, Codierung

codfgm (z,x ) =[ codZ (z) codX (x ) codZ ( f (z,x )) codX (д(z,x )) codM (m(z,x ))]

Beispiel:

wenn ( f ,д,m) (A,2) = (B,1,R)dann codfgm (A,2) = [[00][0][01][1][01]]wenn ( f ,д,m) (C,1) undefiniert

dann codfgm (C,1) = [[10][1][][][]]


Beispielcodierung (5) — eine ganze Turingmaschine


Codierung der gesamten Funktionen:

Konkatenation aller codfgm (z,x ) für alle z ∈ Z , x ∈ X .

Codierung der gesamten Turingmaschine:

Konkatenation von

Codierung des Zustands mit der größten Nummer,

Codierung des Bandsymbols mit der größten Nummer und

Codierung der gesamten Funktionen f , д undmalles eingerahmt von [ ]

Tw bezeichne die Turingmaschine mit Codierung w


Eigenscha�en dieser und ähnlicher Codierungen

einfache Syntaxanalyse ist möglich

man kann TM konstruieren, die für w ∈ A∗ feststellt,

ob es die Codierung einer TM ist oder nicht.

universelle Turingmaschine U existiert

erhält als Eingabe Wort [w1][w2]prü�, ob

w1 Codierung einer Turingmaschine T ist und gegebenenfalls

w2 Codierung einer Eingabe für Tw1

falls nein: entsprechende Mi�eilung und halt

falls ja:

U simuliert Schri� für Schri� die Arbeit,

die Tw1 für Eingabe w2 durchführen würde,

und falls Tw1 endet, liefert U am Ende als Ergebnis

das, was Tw1 liefern würde.











falls ja:















falls ja:















falls ja:






Das Halteproblem ist unentscheidbar

Das Halteproblem ist die formale Sprache

H = {w ∈ A∗ | w ist eine TM-Codierung und Tw (w ) hält.}

SatzDas Halteproblem ist unentscheidbar,

d. h. es gibt keine Turingmaschine, die H entscheidet.

Es gibt Probleme, die man NICHT algorithmisch

also NICHT MIT DEM RECHNER lösen kann!


Es gibt Probleme, die

NICHTalgorithmisch

gelöst werden können!


Diagonalisierung

Beweis der Unentscheidbarkeit von H benutzt

Diagonalisierung.

Idee von Georg Ferdinand Ludwig Philipp Cantor

(1845–1918) (oder früher . . . )

für Überabzählbarkeit von R benutzt

betrachten erst die Kernidee,

danach die Anwendung auf Halteproblem


Diagonalisierung: Kernidee (1)

«zweidimensionale unendliche Tabelle»

Zeilen mit Funktionen fi (i ∈ N0) indiziert

Spalten mit Argumenten w j (j ∈ N0) indiziert

Eintrag in Zeile i und Spalte j: Funktionswert fi (w j )

w0 w1 w2 w3 w4 · · ·

f0 f0 (w0) f0 (w1) f0 (w2) f0 (w3) f0 (w4) · · ·

f1 f1 (w0) f1 (w1) f1 (w2) f1 (w3) f1 (w4) · · ·

f2 f2 (w0) f2 (w1) f2 (w2) f2 (w3) f2 (w4) · · ·

f3 f3 (w0) f3 (w1) f3 (w2) f3 (w3) f3 (w4) · · ·

f4 f4 (w0) f4 (w1) f4 (w2) f4 (w3) f4 (w4) · · ·...

......

......

.... . .



w0 w1 w2 w3 w4 · · ·

f0 f0 (w0) f0 (w1) f0 (w2) f0 (w3) f0 (w4) · · ·

f1 f1 (w0) f1 (w1) f1 (w2) f1 (w3) f1 (w4) · · ·

f2 f2 (w0) f2 (w1) f2 (w2) f2 (w3) f2 (w4) · · ·

f3 f3 (w0) f3 (w1) f3 (w2) f3 (w3) f3 (w4) · · ·

f4 f4 (w0) f4 (w1) f4 (w2) f4 (w3) f4 (w4) · · ·...

......

......

.... . .

d f0 (w0) f1 (w1) f2 (w2) f3 (w3) f4 (w4) · · ·

d f0 (w0) f1 (w1) f2 (w2) f3 (w3) f4 (w4) · · ·



w0 w1 w2 w3 w4 · · ·

f0 f0 (w0) f0 (w1) f0 (w2) f0 (w3) f0 (w4) · · ·

f1 f1 (w0) f1 (w1) f1 (w2) f1 (w3) f1 (w4) · · ·

f2 f2 (w0) f2 (w1) f2 (w2) f2 (w3) f2 (w4) · · ·

f3 f3 (w0) f3 (w1) f3 (w2) f3 (w3) f3 (w4) · · ·

f4 f4 (w0) f4 (w1) f4 (w2) f4 (w3) f4 (w4) · · ·...

......

......

.... . .

d f0 (w0) f1 (w1) f2 (w2) f3 (w3) f4 (w4) · · ·

d f0 (w0) f1 (w1) f2 (w2) f3 (w3) f4 (w4) · · ·



w0 w1 w2 w3 w4 · · ·

f0 f0 (w0) f0 (w1) f0 (w2) f0 (w3) f0 (w4) · · ·

f1 f1 (w0) f1 (w1) f1 (w2) f1 (w3) f1 (w4) · · ·

f2 f2 (w0) f2 (w1) f2 (w2) f2 (w3) f2 (w4) · · ·

f3 f3 (w0) f3 (w1) f3 (w2) f3 (w3) f3 (w4) · · ·

f4 f4 (w0) f4 (w1) f4 (w2) f4 (w3) f4 (w4) · · ·...

......

......

.... . .

d f0 (w0) f1 (w1) f2 (w2) f3 (w3) f4 (w4) · · ·

d f0 (w0) f1 (w1) f2 (w2) f3 (w3) f4 (w4) · · ·

d (wi ) = fi (wi ) =

1 falls fi (wi ) = 00 sonst



w0 w1 w2 w3 w4 · · ·

f0 f0 (w0) f0 (w1) f0 (w2) f0 (w3) f0 (w4) · · ·

f1 f1 (w0) f1 (w1) f1 (w2) f1 (w3) f1 (w4) · · ·

f2 f2 (w0) f2 (w1) f2 (w2) f2 (w3) f2 (w4) · · ·

f3 f3 (w0) f3 (w1) f3 (w2) f3 (w3) f3 (w4) · · ·

f4 f4 (w0) f4 (w1) f4 (w2) f4 (w3) f4 (w4) · · ·...

......

......

.... . .

d f0 (w0) f1 (w1) f2 (w2) f3 (w3) f4 (w4) · · ·

d f0 (w0) f1 (w1) f2 (w2) f3 (w3) f4 (w4) · · ·

d unterscheidet sich von jeder Zeile fi der Tabelle.


Das Halteproblem

SatzEs gibt keine Turingmaschine, die

H = {w ∈ A∗ | w ist eine TM-Codierung und Tw (w ) hält.}

entscheidet.

Beachte:

Es geht um „entscheidet“, nicht nur um „erkennt“.

Es geht um Turingmaschinen, die immer halten.


Beweis der Unentscheidbarkeit des Halteproblems (1)

benutze (eine Variante der) Diagonalisierung

in der Tabelle

Spalten wi : alle Codierungen von Turingmaschinen

Zeilen fi Abbildung mit

fi (w j ) =

1, falls Twi für Eingabe w j hält

0, sonst

für jede Turingmaschine eine Zeile

indirekter Beweis:

Annahme: eine TM Thalt entscheidet Hdann existiert TM Tdiag für die «verdorbene Diagonale»

Widerspruch: verdorbene Diagonale nicht in Tabelle



benutze (eine Variante der) Diagonalisierung

in der Tabelle

Spalten wi : alle Codierungen von Turingmaschinen

Zeilen fi Abbildung mit

fi (w j ) =

1, falls Twi für Eingabe w j hält

0, sonst

für jede Turingmaschine eine Zeile

indirekter Beweis:

Annahme: eine TM Thalt entscheidet Hdann existiert TM Tdiag für die «verdorbene Diagonale»

Widerspruch: verdorbene Diagonale nicht in Tabelle



w j

Hält Tw j (w j )?Thalt

nein ja

wenn es Turingmaschine Thalt gäbe,

dann auch Turingmaschie Tdiag

für Eingabe w jberechne Thalt (w j )

anschließend

würde Tw j (w j ) nicht halten, dann halte

würde Tw j (w j ) halten, dann halte nicht

für jedes w j in beiden Fällen

verhält sich Tdiag anders als Tw j

also wäre TM Tdiag anders als jede TM



w j

Tdiag


nein

stop

ja




anschließend








w j

Tdiag


nein

stop

ja




anschließend







Weitere unentscheidbare Probleme

Varianten des Halteproblems

Beispiel:

Hält gegebene TM, wenn das Band zu Beginn völlig leer ist?

Äquivalenzproblem:

Liefern zwei TM für jede Eingabe die gleiche Ausgabe?

automatischer Vergleich mit „Musterlösungen“ unmöglich

Wird ein bestimmter Zustand einer TM jemals gebraucht?

Erreichbarkeit von Codestücken unentscheidbar

vieles vieles vieles vieles vieles vieles vieles mehr

Beachte: sta� Turingmaschine kann man immer

Java-Programm einsetzen


Erinnerung: BB3

Bandalphabet ist X = {2,1}.

Turingmaschine hat 3 + 1 Zustände

in 3 Zuständen für jedes Bandsymbol Fortsetzung definiert

einer dieser 3 Zustände ist Anfangszustand

in Zustand 4 für kein Bandsymbol Fortsetzung

(„Haltezustand“).

Wenn man die Turingmaschine auf dem leeren Band startet,

dann hält sie nach endlich vielen Schri�en.


Bibermaschinen

n-Bibermaschine:

Bandalphabet ist X = {2,1}.Turingmaschine hat n + 1 Zustände

in n Zuständen für jedes Bandsymbol Fortsetzung definiert

einer dieser n Zustände ist Anfangszustand

in Zustand n + 1 für kein Bandsymbol Fortsetzung

(„Haltezustand“).

Wenn man die TM auf dem leeren Band startet,

dann hält sie nach endlich vielen Schri�en.

im folgenden zu Beginn immer vollständig leeres Band


Fleißige Biber und die Busy-Beaver-Funktion

Busy-Beaver-Funktion (oder Radó-Funktion)

bb : N+ → N+bb(n) = maximale Anzahl von Einsen, die

n-Bibermaschine am Ende

auf dem Band hinterlässt

fleißiger Biber: n-Bibermaschine die bb(n) Einsen scha�t


Busy-Beaver-Funktion —

Schranken für einige Funktionswerte

n bb(n)

1 12

4 Radó (1963)

3

6 Radó (1963)

4

13 Brady (1974(?))

5

≥ 4098 Marxen/Buntrock (1990)

6

> 3.514 · 1018276 Kropitz (2010)

...

...




n bb(n)

1 12 4 Radó (1963)

3

6 Radó (1963)

4

13 Brady (1974(?))

5


6

> 3.514 · 1018276 Kropitz (2010)

...

...




n bb(n)

1 12 4 Radó (1963)

3 6 Radó (1963)

4

13 Brady (1974(?))

5


6

> 3.514 · 1018276 Kropitz (2010)

...

...




n bb(n)

1 12 4 Radó (1963)

3 6 Radó (1963)

4 13 Brady (1974(?))

5


6

> 3.514 · 1018276 Kropitz (2010)

...

...




n bb(n)

1 12 4 Radó (1963)

3 6 Radó (1963)

4 13 Brady (1974(?))

5 ≥ 4098 Marxen/Buntrock (1990)

6

> 3.514 · 1018276 Kropitz (2010)

...

...




n bb(n)

1 12 4 Radó (1963)

3 6 Radó (1963)

4 13 Brady (1974(?))

5 ≥ 4098 Marxen/Buntrock (1990)

6 > 3.514 · 1018276 Kropitz (2010)

......


Die Busy-Beaver-Funktion ist nicht berechenbar

Satz

Für jede totale berechenbare Funktion f : N+ → N+gibt es ein n0 so, dass ∀n ≥ n0 : bb(n) > f (n).

Korollar

Die Busy-Beaver-Funktion bb(n) ist nicht berechenbar.


Was ist wichtig


Das Halteproblem ist unentscheidbar.

viele andere interessierende Probleme auch

Busy-Beaver-Funktion wächst schneller

als jede berechenbare Funktion.


informelle algorithmische Beschreibungen

in Turingmaschinen überführen


Steam-Powered Turing Machine ;-)http://www.cs.washington.edu/homes/ruzzo/„[. . . ] principal research project involves the construction andprogramming [. . . ] of 32 steam-powered Turing machines“„Graduate students have played an important role in theconstruction and operation of the engine [. . . ] advancedundergraduates are occasionally allowed to polish the brassgauges.““Originally intended as a general computing engine, restrictionsimposed by the Pollution Control and Noise Abatement Boardsrequire that only algorithms running in polynomial time may beused.“„one of [the] students slipped on a mouldering stack of ungradedhomework exercises and fell under the write head of one of themachines. Now permanently embossed with a series of 1’s and 0’s,the student is suing to have the machine dismantled.“


http://www.cs.washington.edu/homes/ruzzo/

Zusammenfassung

Turingmaschinen sind eine formale Präzisierung des

Algorithmusbegri�s.

Komplexitätsmaße und Komplexitätsklassen

insbesondere P und PSPACEim 3. Semester: P ⊆ NP ⊆ PSPACE

Es gibt Probleme, die anscheinend sehr großen

algorithmischen Aufwand erfordern.

Es gibt Probleme, die beweisbar sehr großen

algorithmischen Aufwand erfordern.

Es gibt Probleme, die algorithmisch gar nicht lösbar sind.


Documents

Kapitel 20: Turingmaschinen Thomas Worschgbi.ira.uka.de/vorlesungen/k-20-turingmaschinen-folien.pdf · Grundbegri˙e der Informatik Kapitel 20: Turingmaschinen Thomas Worsch KIT,