André Vratislavsky
Übungsgruppe vom 14.12.99
Unentscheidbare Sprachen
Wir hatten entscheidbare Sprachen und Turingmaschinen, die solche erkennen,
kennengelernt.
Nun stellt sich die Frage, ob es Sprachen gibt, die nicht entscheidbar,
d.h. nicht berechenbar sind. Es stellt sich heraus, daß eine solche
Sprache gefunden werden kann. Dazu definieren wir die Universelle
TM, die eine beliebige durch ihre Gödelnummer
kodierte TM und ein beliebiges Wort als Eingabe erhält und diese TM
mit diesem Wort als Eingabe simuliert (Definition und Existenz siehe
Vorlesung).
Die erste unentscheidbare Sprache, die wir kennenlernen, ist die sogenannt
Diagonalsprache LD, die aus allen Gödelnummern
besteht, welche sich selbst als Eingabe nicht akzeptieren.
Das Komplement von LD ist ebenfalls nicht rekursiv,
da die rekursiven Sprachen unter Komplementbildung abgeschlossen sind.
Weitere unentscheidbare Sprachen lassen sich mit dem sogenannten Rekursionsschema
beweisen.
A '<=' B bedeutet dabei: B ist "mindestens so schwierig"
wie A.
L1 ist auf L2 reduzierbar (L1'<='
L2)
gdw. es eine überall def. berechenbare Funktion f gibt,
so daß für alle Wörter w gilt: w aus L1 <=>
f(w) aus L2
Aus dieser Definition folgt:
L1 nicht rekursiv => L2 nicht rekursiv
Bew.:
Wenn L2 rekursiv ist, können wir entscheiden, ob w
in L2 ist.
Dann mache folgendes:
- Berechne f(w) (möglich, da f rekursiv und überall definiert).
- Entscheide, ob f(w) in L2 ist.
Da (w aus L1 <=> f(w) aus L2), ist es entscheidbar,
ob w in L1 ist; L1 ist also rekursiv.
Durch Kontraposition folgt die Behauptung.
Die umgekehrte Behauptung(L2 nicht rekursiv => L1
nicht rekursiv) kann nicht gezeigt werden, da wir für jedes w
aus L2 ein Urbild bräuchten.