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
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 2 / 73
Wo sind wir?
Eine technische Vorbemerkung
Turingmaschinen
Berechnungskomplexität
Unentscheidbare Probleme
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 3 / 73
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
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 4 / 73
Wo sind wir?
Eine technische Vorbemerkung
Turingmaschinen
Berechnungskomplexität
Unentscheidbare Probleme
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 5 / 73
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
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 6 / 73
Eine Turingmaschine im Bild
z
· · · 2 2 a b b a a 2 · · ·
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 7 / 73
Eine Turingmaschine im Bild
z
· · · 2 2 a b b a a 2 · · ·
Steuereinheit: endliche Zustandsmenge Z
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 8 / 73
Eine Turingmaschine im Bild
z
· · · 2 2 a b b a a 2 · · ·
endliche Zustandsmenge Z
Band, in Felder unterteilt:
beschri�et mit Symbolen aus Bandalphabet X
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 9 / 73
Eine Turingmaschine im Bild
z
· · · 2 2 a b b a a 2 · · ·
endliche Zustandsmenge Z
Bandalphabet X
nächste Aktion festgelegt durch
aktuellen Zustand z und
aktuell gelesenes Symbol x
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 10 / 73
Eine Turingmaschine im Bild
z
· · · 2 2 a b b a a 2 · · ·
endliche Zustandsmenge Z
Bandalphabet X
Schri�
neue Feldbeschri�ung д(z,a)neuer Zustand f (z,a)Kopfbewegungm(z,a)
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 11 / 73
Eine Turingmaschine im Bild
z ′
· · · 2 2 c b b a a 2 · · ·
endliche Zustandsmenge Z
Bandalphabet X
Schri�:
neue Feldbeschri�ung д(z,a) = cneuer Zustand f (z,a) = z ′
Kopfbewegungm(z,a) = +1
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 12 / 73
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
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 13 / 73
Turingmaschinen: graphische Darstellung (TM BB3)
A
H
B
C
2 |1R
1 |1R
2 |2R
1 |1R
2 |1L
1 |1L
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 14 / 73
Turingmaschinen: graphische Darstellung
A
B
C
2 |1R
2 |2R
1 |1R
2 |1L
1 |1L
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 14 / 73
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 . . .
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 15 / 73
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
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 16 / 73
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
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 16 / 73
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
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 16 / 73
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
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 16 / 73
Beispielberechnung (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
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 17 / 73
Beispielberechnung (3)
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
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 18 / 73
Beispielberechnung (4)
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
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 19 / 73
Beispielberechnung (5)
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
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 20 / 73
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
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 21 / 73
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
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 22 / 73
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
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 23 / 73
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
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 24 / 73
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» ?
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 25 / 73
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
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 26 / 73
zwei Arten von Turingmaschinen
Berechung von Funktionen
Erkennung formaler Sprachen
Turingmaschinenakzeptoren
Entscheidungsprobleme
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 27 / 73
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 . . .
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 28 / 73
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
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 29 / 73
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
erstes und letztes Symbol übereinstimmen
und dazwischen ein Palindrom steht
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 30 / 73
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
erstes und letztes Symbol übereinstimmen
und dazwischen ein Palindrom steht
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 30 / 73
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
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 31 / 73
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
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 31 / 73
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
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 32 / 73
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
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 33 / 73
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
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 34 / 73
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
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 35 / 73
Wo sind wir?
Eine technische Vorbemerkung
Turingmaschinen
Berechnungskomplexität
Unentscheidbare Probleme
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 36 / 73
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.
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 37 / 73
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.
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 37 / 73
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)
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 38 / 73
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
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 39 / 73
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
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 40 / 73
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)
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 41 / 73
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.
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 42 / 73
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.
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 43 / 73
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.
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 44 / 73
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
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 45 / 73
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 ?
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 46 / 73
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 ?
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 46 / 73
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 ?
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 46 / 73
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 ?
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 46 / 73
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 ?
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 46 / 73
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 ?
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 46 / 73
Was ist wichtig
Das sollten Sie mitnehmen:
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
Das sollten Sie üben:
Abschätzung der Zeit- und Raumkomplexität von TM
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 47 / 73
Wo sind wir?
Eine technische Vorbemerkung
Turingmaschinen
Berechnungskomplexität
Unentscheidbare Probleme
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 48 / 73
Achtung Achtung Achtung Achtung Achtung Achtung
Ab sofort ist es wieder von Bedeutung, dass
Turingmaschinen in «Endlosschleifen» laufen können.
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 49 / 73
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/
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 50 / 73
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/
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 50 / 73
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]. . .
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 51 / 73
Beispielcodierung (2) — Symbole
Turingmaschine T = (Z , z0,X ,2, f ,д,m)
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]. . .
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 52 / 73
Beispielcodierung (3) — Kopfbewegungen
Turingmaschine T = (Z , z0,X ,2, f ,д,m)
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]
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 53 / 73
Beispielcodierung (4) — einzelne Funktionswerte
Turingmaschine T = (Z , z0,X ,2, f ,д,m)
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][][][]]
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 54 / 73
Beispielcodierung (5) — eine ganze Turingmaschine
Turingmaschine T = (Z , z0,X ,2, f ,д,m)
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
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 55 / 73
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.
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 56 / 73
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.
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 56 / 73
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.
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 56 / 73
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.
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 56 / 73
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!
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 57 / 73
Es gibt Probleme, die
NICHTalgorithmisch
gelöst werden können!
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 58 / 73
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
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 59 / 73
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) · · ·...
......
......
.... . .
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 60 / 73
Diagonalisierung: Kernidee (2)
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) · · ·
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 61 / 73
Diagonalisierung: Kernidee (2)
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) · · ·
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 61 / 73
Diagonalisierung: Kernidee (2)
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
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 61 / 73
Diagonalisierung: Kernidee (2)
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.
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 61 / 73
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.
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 62 / 73
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
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 63 / 73
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
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 63 / 73
Beweis der Unentscheidbarkeit des Halteproblems (2)
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
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 64 / 73
Beweis der Unentscheidbarkeit des Halteproblems (2)
w j
Tdiag
Hält Tw j (w j )?Thalt
nein
stop
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
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 64 / 73
Beweis der Unentscheidbarkeit des Halteproblems (2)
w j
Tdiag
Hält Tw j (w j )?Thalt
nein
stop
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
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 64 / 73
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
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 65 / 73
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.
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 66 / 73
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
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 67 / 73
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
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 68 / 73
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)
...
...
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 69 / 73
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)
...
...
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 69 / 73
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)
...
...
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 69 / 73
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)
...
...
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 69 / 73
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)
...
...
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 69 / 73
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)
......
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 69 / 73
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.
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 70 / 73
Was ist wichtig
Das sollten Sie mitnehmen:
Das Halteproblem ist unentscheidbar.
viele andere interessierende Probleme auch
Busy-Beaver-Funktion wächst schneller
als jede berechenbare Funktion.
Das sollten Sie üben:
informelle algorithmische Beschreibungen
in Turingmaschinen überführen
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 71 / 73
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.“
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 72 / 73
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.
GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 73 / 73