null

S
e
i
t
e
2
Z
w
i
s
c
h
e
n
t
i
t
e
l
Inhalt
– Konzept der Turingmaschine
|
L
e
i
t
t
h
e
m
a
o
d
e
r
N
a
m
e
|
D
a
t
u
m
– Beispiele
– Bedeutung der Turingmaschine und Anwendungen
S
e
i
t
e
3
Z
w
i
s
c
h
e
n
t
i
t
e
l
Alan Turing
– Britischer Mathematiker (1912 - 1954)
|
L
e
i
t
t
h
e
m
a
o
d
e
r
N
a
m
e
|
D
a
t
u
m
– Codeknacker im 2. Weltkrieg
– Erfinder der Turingmaschine und
Begründer der Berechenbarkeitstheorie
– 1936: „On computable numbers with an application to the
Entscheidungsproblem“
S
e
i
t
e
4
Z
w
i
s
c
h
e
n
t
i
t
e
l
Turingmaschine
– Abstraktes Modell einer Rechenmaschine
– Bestandteile:
|
L
e
i
t
t
h
e
m
a
o
d
e
r
N
a
m
e
|
D
a
t
u
m
●
Unendlich langes Speicherband, in einzelne Felder unterteilt
●
Schreib-/Lesekopf, der auf dem Band operiert
●
Endliche Steuereinheit („Programm“)
S
e
i
t
e
5
Z
w
i
s
c
h
e
n
t
i
t
e
l
Turingmaschine
– Funktionsweise (informell)
●
|
L
e
i
t
t
h
e
m
a
o
d
e
r
N
a
m
e
|
D
a
t
u
m
●
●
Jedes Feld auf dem Band kann ein Zeichen enthalten.
Schreib-/Lesekopf wandert über das Band und manipuliert die
Zeichen
Programm kann auf dem aktuellen Feld lesen und schreiben und
den Kopf um ein Feld nach links oder rechts bewegen
S
e
i
t
e
6
Z
w
i
s
c
h
e
n
t
i
t
e
l
Turingmaschine
– Funktionsweise (informell)
●
|
L
e
i
t
t
h
e
m
a
o
d
e
r
N
a
m
e
|
D
a
t
u
m
Eingabe besteht aus endlich vielen Zeichen eines endlichen
Eingabealphabets und steht initial auf dem Band.
Der Schreib-/Lesekopf steht auf dem ersten Zeichen der Eingabe
●
Ausgabe ist der Zustand des Bands, nachdem das Programm
gestoppt hat
S
e
i
t
e
7
Z
w
i
s
c
h
e
n
t
i
t
e
l
Turingmaschine
– Funktionsweise (informell)
●
|
L
e
i
t
t
h
e
m
a
o
d
e
r
N
a
m
e
|
D
a
t
u
m
Steuereinheit wird durch eine Überführungsfunktion beschrieben
Endliche Menge an Zuständen
●
Zustand und Zeichen auf dem aktuellen Feld bestimmen
ausgeführte Aktion (Schreiben, Bewegen, Zustandsübergang)
S
e
i
t
e
8
Z
w
i
s
c
h
e
n
t
i
t
e
l
Turingmaschine
– Entscheidungsproblem
●
|
L
e
i
t
t
h
e
m
a
o
d
e
r
N
a
m
e
|
D
a
t
u
m
●
Turingmaschine entscheidet, ob Eingabe eine bestimmte
Eigenschaft besitzt
Befindet sich die TM nach Ablauf des Programms in einem sog.
Endzustand, lautet die Antwort ja, sonst nein
S
e
i
t
e
9
Z
w
i
s
c
h
e
n
t
i
t
e
l
Turingmaschine
|
L
e
i
t
t
h
e
m
a
o
d
e
r
N
a
m
e
|
D
a
t
u
m
– Turingmaschine berechnet insbesondere eine (partielle) Funktion
– Zahlen können durch g-Bruchentwicklung als Wörter über einem
Alphabet dargestellt werden
– Allgemein kann jede abzählbare Menge durch z.B. 0en und 1en codiert
werden
S
e
i
t
e
10
Z
w
i
s
c
h
e
n
t
i
t
e
l
Beispiele
|
L
e
i
t
t
h
e
m
a
o
d
e
r
N
a
m
e
|
D
a
t
u
m
S
e
i
t
e
11
Z
w
i
s
c
h
e
n
t
i
t
e
l
Berechenbarkeit
|
L
e
i
t
t
h
e
m
a
o
d
e
r
N
a
m
e
|
D
a
t
u
m
– Church-Turing-These:
Die Klasse der turing-berechenbaren Funktionen stimmt mit der Klasse
der intuitiv berechenbaren Funktionen überein
→ Nicht jede Funktion ist berechenbar
– Eine Turingmaschine kann jedes andere Berechnungsmodell ersetzen
→ alles was ein moderner Computer kann, kann auch durch eine
Turingmaschine berechnet werden
→ Sogar Quantencomputer können nicht mehr als eine Turingmaschine
berechnen kann (sind jedoch um ein Vielfaches schneller)
→ Turingmaschinen können auch Turingmaschinen simulieren (siehe
gleich)
– Modelle, die ihrerseits Turingmaschinen simulieren können, heißen
turingvollständig
S
e
i
t
e
12
Z
w
i
s
c
h
e
n
t
i
t
e
l
Universelle Turingmaschine
|
L
e
i
t
t
h
e
m
a
o
d
e
r
N
a
m
e
|
D
a
t
u
m
– Die Universelle Turingmaschine ist eine Turingmaschine, die jede
andere Turingmaschine simulieren kann
– Eingabe: beliebige Turingmaschine M + Eingabewort x
– Ausgabe: Ausgabe, die M auf x machen würde
S
e
i
t
e
13
Z
w
i
s
c
h
e
n
t
i
t
e
l
Halteproblem
|
L
e
i
t
t
h
e
m
a
– Frage (allgemein formuliert): Kann man eindeutig feststellen, ob ein
Computerprogramm für eine bestimmte Eingabe nach endlicher Zeit
stoppt?
– Antwort: NEIN!
o
d
e
r
N
a
m
e
|
D
a
t
u
m
– Gegeben eine Turingmaschine M und eine Eingabe x
Frage: Stoppt M auf x?
S
e
i
t
e
14
Z
w
i
s
c
h
e
n
t
i
t
e
l
Halteproblem
– Gegeben eine Turingmaschine M und eine Eingabe x
Frage: Stoppt M auf x?
|
L
e
i
t
t
h
e
m
a
o
d
e
r
N
a
m
e
|
D
a
t
u
m
Annahme: diese Frage kann allgemein algorithmisch beantwortet
werden
– Dann ist folgende Funktion berechenbar
S
e
i
t
e
15
Z
w
i
s
c
h
e
n
t
i
t
e
l
Halteproblem
|
L
e
i
t
t
h
e
m
a
o
d
e
r
N
a
m
e
|
D
a
t
u
m
– Dann existiert auch eine TM T, die die Funktion in endliche vielen
Schritten berechnet
– Konstruiere die TM T'
●
●
Eingabe: beliebige Turingmaschine M
Programm: T' simuliert T mit Eingabe (M, M). Nach endlich vielen
Schritten liegt ein Ergebnis vor
–
Falls 1 geht T' in eine Endlosschleife
–
Falls 0 stoppt T' und gibt 1 aus
S
e
i
t
e
16
Z
w
i
s
c
h
e
n
t
i
t
e
l
Halteproblem
– Konstruiere die TM T'
●
|
●
L
e
i
t
t
h
e
m
a
o
d
e
r
N
a
m
e
|
D
a
t
u
m
Eingabe: beliebige Turingmaschine M
Programm: T' simuliert T mit Eingabe (M, M). Nach endlich vielen
Schritten liegt ein Ergebnis vor
–
Falls 1 geht T' in eine Endlosschleife
–
Falls 0 stoppt T und gibt 1 aus
– Was passiert, wenn man T' in T' eingibt?
●
T' Gibt stoppt genau dann, wenn T null ausgibt
●
T gibt genau dann 0 aus, wenn M angesetzt auf M nicht stoppt
●
M ist hier aber die Eingabe von T', also T' selbst
→ T' stoppt genau dann, wenn T' nicht stoppt
→ Eine solche Maschine T kann nicht existieren
→ Die Funktion ist nicht berechenbar und damit das Halteproblem nicht
entscheidbar
S
e
i
t
e
17
Z
w
i
s
c
h
e
n
t
i
t
e
l
Quellen
–
in, Routledge, Encyclopedia of Philosophy, London/New York 1998.
|
–
Church-Turing These (Stanford Encyclopedia of Philosophy
L
e
i
t
t
h
e
m
a
–
Wikipedia (Turingmaschine, Alan Turing, Halteproblem)
–
U. Schöning, J. Toran: Berechenbarkeit und Komplexität
o
d
e
r
N
a
m
e
|
D
a
t
u
m

Download Report