II. Entscheidbarkeit
1. Entscheidbarkeit und Semi-Entscheidbarkeit
Vorbemerkungen:
a) Berechenbare Funktionen bisher: Funktionen auf natürlichen Zahlen.
Ausnahme Turing-Berechenbarkeit: auch schon definiert für Funktionen f: * *.
Lässt sich für andere Berechenbarkeitsbegriffe über Codierungen in natürliche Zahlen analog einführen:
seien code: * INund decode: IN * totale Turing-berechenbare Funktionen, so dass decode(code(w)) = w.
(solche Codierungs- und Decodierungsfunktionen lassen sich immer finden, z.B. kann man jedes Wort über dem Alphabet {a1, ..., ak} als Zahl zur Basis k+1 lesen).
Wir sagen f: * * ist WHILE berechenbar, wenn es WHILE berechenbare Funktion g gibt mit f(w) = w’ gdw decode(g(code(w)) = w’.
Ähnlich für andere Berechenbarkeitsbegriffe.
b) Sei M TM zur Berechnung von f. Aus M kann eine TM M’ konstruiert werden, die testet, ob M nach s Schritten stoppt.
Grundidee: weiteres Band j, initialisiert mit s. Nach jedem Konfigurationsübergang von M wird Band j um 1 dekrementiert.
M stoppt bevor Band j = 0 => stoppe mit Ausgabe 0
Band j = 0 bevor M stoppt => stoppe mit Ausgabe 0
M stoppt und gleichzeitig Band j = 0 => stoppe mit Ausgabe 1
Def. : Eine Menge A * heißt entscheidbar, gdw. die charakteristische Funktion von A
A: * {0,1}
mit A(w) = 1 falls w A
falls w A
berechenbar ist.
Eine Menge A * heißt semi-entscheidbar, gdw. die "halbe" charakteristische Funktion von A
'A: * {0,1}
mit 'A(w) = 1 falls w A
undefiniert falls w A
berechenbar ist.
ja
entscheidbar: w -> terminiert immer
nein
ja
semi-entscheidbar: w ->
undefiniert
Satz: A ist entscheidbar gdw A (das Komplement von A) entscheidbar ist.
Beweis: um aus einer TM M, die A entscheidet, eine TM zu erzeugen, die das Komplement von A entscheidet, sind nur die Ausgabewerte 1 und 0 zu vertauschen. Dazu ist M nur mit einer entsprechenden TM für das Vertauschen dieser Werte hintereinander zu schalten. Entsprechendes gilt für die umgekehrte Richtung.
Satz: A ist entscheidbar gdw A und A (das Komplement von A) semi-entscheidbar sind.
Beweis: "=>" offensichtlich, TM geht bei 0 bzw. 1 in Endlosschleife (im Fall des Komplements 0 in 1 umwandeln).
"<=" TM M1 berechnet 'A, M2 berechnet 'A. Konstruiere TM M, die A entscheidet, auf folgende Weise: M führt abwechselnd einen Schritt von M1 und einen von M2 aus. Wenn M1 mit 1 terminiert, gibt M 1 aus. Wenn M2 mit 1 terminiert, gibt M 0 aus.
Def.: A * heißt rekursiv aufzählbar gdw A = oder es gibt eine totale berechenbare Funktion f: IN *, so dass A = {f(0), f(1), f(2), ... }.
(Anmerkung: f(i) = f(j) für i j zulässig).
Satz: Eine Sprache ist rekursiv aufzählbar gdw sie semi-entscheidbar ist.
Beweis: "=>" Sei f Funktion, die A aufzählt. Die TM, die 'A berechnet, lässt sich so beschreiben:
INPUT(x)
FOR n := 0,1,2, 3, … DO
IF f(n) = x THEN OUTPUT(1) END
END
Anmerkung: wir verwenden hier eine Programmiersprachennotation für Turingmaschinen. Gemeint ist die Mehrband-TM M, die gestartet mit x auf dem Eingabeband und 0 auf dem Band n die TM M’ zur Berechnung von f(n) ausführt (Eingabeband von M’ ist Band n). Falls das Ergebnis der Berechnung von M’ identisch mit x ist, schreibt M 1 auf das Ausgabeband, ansonsten wird n inkrementiert usw.
"<=" A sei semi-entscheidbar mittels M, a festes Element aus A. Gesucht ist eine totale berechenbare Funktion f mit Wertebereich A. Folgende (in Programmiersprachennotation beschriebene) TM berechnet ein solches f:
INPUT(n);
x:= ec(n);
y:= fc(n);
w := decode(x);
IF M gestartet mit Eingabe w stoppt nach y Schritten THEN OUTPUT(w) ELSE OUTPUT(a)
n ist die Codierung eines Paares natürlicher Zahlen (x,y), x ist Codierung eines Wortes aus *, decode(x) liefert dasjenige Wort aus *, das als x codiert wird. Der Algorithmus ist total, gibt nur Worte aus A aus. Noch zu zeigen: jedes Element aus A wird ausgegeben. Sei w beliebiges Wort aus A, z der Code von w. Sei n = c(z,s), wobei s die Zahl der Schritte ist, die M braucht, um bei Eingabe von w mit Ausgabe 1 zu terminieren. Nach Konstruktion liefert der Algorithmus w bei Eingabe n.
Satz: Folgende Aussagen sind äquivalent:
A ist rekursiv aufzählbar.
A ist semi-entscheidbar.
A ist vom Typ 0.
A = T(M) für eine Turingmaschine M.
'A ist berechenbar.
A ist der Definitionsbereich einer berechenbaren Funktion.
A ist der Wertebereich einer berechenbaren Funktion.
Beweis:
1 <=> 2 soeben bewiesen; 3 <=> 4 im letzten Semester (Vorlesung Automaten und Sprachen) gezeigt; 2 <=> 5 Definition.
4 => 5 akzeptierende TM M wird so modifiziert, dass Ausgabe 1 produziert wird.
5 => 4 TM für 'A ist gleichzeitig auch akzeptierende TM für A.
5 => 6 Definitionsbereich von 'A ist gerade A.
6 => 5 wenn A Definitionsbereich von f ist, dann kann 'A berechnet werden, indem die Ausgabe von f mit 1 überschrieben wird.
1 => 7 Definition.
7 => 1 Konstruiere Aufzählungsfunktion h auf Basis von g mit Wertebereich A so:
h(n) = a, falls g bei Eingabe e(n) nach f(n) Schritten a liefert
a’ sonst, wobei a’ beliebiges festes Element von A ist.
(Falls g nicht IN als Definitionsbereich hat, muss der Definitionsbereich von g erst noch in die natürlichen Zahlen codiert werden).
Bemerkung: der Begriff „höchstens abzählbar“ (= endlich oder abzählbar unendlich) kann wie rekursive Aufzählbarkeit definiert werden (Existenz einer surjektiven Funktion von IN in die betreffende Menge1), aber f muss nicht berechenbar sein.
Teilmengen höchstens abzählbarer Mengen sind höchstens abzählbar: sei A' A, f Abzählung von A, a beliebiges Element aus A'. Dann ist
g(n) = f(n) falls f(n) A'
a sonst
Abzählung von A. Aber: g nicht notwendiger Weise berechenbar, selbst wenn f berechenbar.
| 