2. Nicht-entscheidbare Probleme: das Halteproblem
Codierung von Turingmaschinen als Wort über {0,1}.
Sei = {a0, ..., ak}, Z = {z0, ..., zn}, z0 Startzustand, zn Endzustand (jede TM kann in eine äquivalente mit genau 1 Endzustand überführt werden).
Für jede -Regel: (zi, aj) = (zi', aj', y)
zugeordnetes Wort: ##bin(i)#bin(j)#bin(i')#bin(j')#bin(m)
wobei m = 0 falls y = L
1 falls y = R
2 falls y = N
alle so erzeugten Wörter in beliebiger Reihenfolge ergeben Wort über {0,1,#}
daraus wird Wort über {0,1} erzeugt durch Codierung, etwa
0 -> 00
1 -> 01
# -> 11
Nicht jedes Wort ist der Code einer Turingmaschine, deshalb:
Sei M^ beliebige, feste Turingmaschine. Für jedes w {0,1}* definieren wir:
Mw = M falls w Code der Turingmaschine M ist
M^ sonst
Def.: Das spezielle Halteproblem (Selbstanwendbarkeitsproblem) ist die Sprache
K = { w {0,1}* | Mw hält bei Eingabe w}
Satz: Das spezielle Halteproblem ist nicht entscheidbar.
Motivation des Beweises: Betrachte die folgende unendliche Tabelle, die angibt, ob Mwi bei Eingabe wj anhält (1) oder nicht (0). w0, w1, w2, … ist eine Aufzählung von {0,1}* (die Einträge in der folgenden Tabelle sind willkürlich gewählt). Die Einträge in der Diagonale geben an, ob eine TM bei Eingabe ihres eigenen Codes hält oder nicht:
input\TM
|
Mw0
|
Mw1
|
Mw2
|
Mw3
|
…
|
w0
|
0
|
1
|
0
|
0
|
|
w1
|
1
|
0
|
1
|
1
|
|
w2
|
0
|
0
|
1
|
1
|
|
w3
|
1
|
1
|
0
|
0
|
|
…
|
|
|
|
|
|
Der Beweis konstruiert eine Turingmaschine M’, die bei Eingabe wi das dem Terminierungsverhalten von Mwi (bei derselben Eingabe) gegenteilige Verhalten aufweist. Da M’ selber in der Aufzählung der Turingmaschinen vorkommen muss, müsste sich das Terminierungsverhalten von M’ an mindestens einer Stelle von sich selbst unterscheiden, was nicht sein kann.
Bew.: Angenommen K ist entscheidbar. Dann gibt es eine Turingmaschine M, die K berechnet. Aus dieser TM lässt sich folgende Turingmaschine M' konstruieren:
start
M
Band = 0?
nein ja
stop
M' stoppt genau dann wenn M 0 berechnet, sonst geht M' in Endlosschleife.
Sei w' der Code von M'. Es gilt:
M' hält bei Eingabe w' M berechnet 0 bei Eingabe w'
K (w') = 0
w' K
Mw' hält nicht bei Eingabe w'
M' hält nicht bei Eingabe w'
Widerspruch, damit muss die Annahme, K sei entscheidbar, falsch sein.
Unentscheidbarkeitsbeweise häufig durch Reduktion:
Def.: Eine Sprache A * heißt reduzierbar auf eine Sprache B * (A B), genau dann wenn es eine totale berechenbare Funktion f: * -> * gibt, so dass für alle w *:
w A f(w) B.
Intuitiv: wenn A auf B reduzierbar ist, dann beinhaltet eine Lösung des Entscheidungs-problems von B eine Lösung von A. Es ist also mindestens so schwer, B zu entscheiden, wie A zu entscheiden.
Lemma: Falls A B und B (semi-)entscheidbar, so ist auch A (semi-)entscheidbar.
Beweis: Sowohl f wie B sind berechenbar, damit auch ihre Komposition B f. Es gilt
A = B f
denn
A(w) = 1 w A f(w) B B(f(w)) = 1
und
A(w) = 0 w A f(w) *\B B(f(w)) = 0
Analog für 'A.
Oft Kontraposition des Lemmas verwendet: A unentscheidbar => B unentscheidbar.
Def.: Das (allgemeine) Halteproblem ist die Sprache
H = {w#x | w, x {0,1}*, Mw hält bei Eingabe x}
Satz: Das Halteproblem ist nicht entscheidbar.
Beweis: K H, denn für f(w) = w#w gilt: f ist total, offensichtlich berechenbar, und außerdem w K f(w) H.
Def.: Das Halteproblem bei leerem Band ist die Sprache
H0 = {w {0,1}* | Mw hält bei leerer Eingabe}
Satz: Das Halteproblem bei leerem Band ist nicht entscheidbar.
Beweis: wir zeigen H H0. Jedem Wort w#x kann man eine Turingmaschine Mw#x zuordnen, die gestartet mit leerem Band zuerst x auf das Band schreibt, danach Mw ausführt. Man kann zeigen, dass die Funktion f, die w#x den Code von Mw#x zuordnet, total und berechenbar ist. Es gilt w#x H gdw. f(w#x) H0, d.h. wir haben H auf H0 reduziert und H0 ist unentscheidbar, da H unentscheidbar ist.
Der folgende wichtige Satz geht auf Henry Gordon Rice zurück. Er besagt, dass es keinen Algorithmus geben kann, der bei Eingabe (des Codes einer) Turingmaschine entscheidet, ob diese eine Funktion berechnet, die zu einer vorgegebenen, nicht-trivialen Klasse von berechenbaren Funktionen gehört (eine nicht-triviale Klasse enthält mindestens eine berechenbare Funktion, aber nicht alle).
Beispiele: konstante Funktionen; totale Funktionen; Funktionen, die bei bestimmter Eingabe k terminieren; Funktionen, bei denen für mindestens eine Eingabe den Wert k produziert; usw.
Satz (Rice, 1953): Sei R die Klasse aller Turing-berechenbaren Funktionen, S echte Teilmenge von R. Dann ist
C(S) = {w {0,1}* | die von Mw berechnete Funktion liegt in S}
unentscheidbar.
Beweisskizze: falls die überall undefinierte Funktion in S liegt, kann man H0 auf C(S) reduzieren, falls sie nicht in S liegt H0 auf C(S). (Bemerkung: da H0 unentscheidbar, muss auch das Komplement unentscheidbar sein.)
Anmerkung 1: wenn A B und B A, so sind A und B "gleich schwer". Es gibt eine unendliche Folge von immer schwereren Problemen.
Anmerkung 2: Man kann eine universelle Turingmaschine U konstruieren, die bei Eingabe von w#x die Berechnung von Mw bei Eingabe x durchführt.
Anmerkung 3: H ist rekursiv aufzählbar. Aus der universellen Turingmaschine U lässt sich folgendermaßen ein Aufzählungsverfahren konstruieren:
Sei w’#x’ ein beliebiges, festes Wort so dass Mw’ bei Eingabe x’ hält. Definiere
f(n) = w#x, falls w = bin(d0(n)), x = bin(d1(n)) und
U hält bei Eingabe w#x nach d2(n) Schritten
w’#x’ sonst.
di sind hier die Decodierfunktionen, d.h. n wird als Codierung von 3 Zahlen aufgefasst, die erste ist der Code einer TM, die zweite die Eingabe, die dritte eine vorgegebene Schrittzahl.
Anmerkung 4: Aus der rekursiven Aufzählbarkeit von H folgt zusammen mit der Unentscheidbarkeit sofort, dass das Komplement von H nicht rek. aufzählbar sein kann.
|
