André Vratislavsky
Übungsgruppe vom 30.11./7.12.99
Entscheidbarkeit
Wir hatten eine Sprache als Menge von Zeichenketten definiert und die Sprachklasse
der regulären Sprachen behandelt. Jetzt werden die rekursiven und
rekusiv aufzählbaren Sprachen eingeführt.
Die zugrunde liegende Frage dazu ist die der Berechenbarkeit.
Im folgenden sollen die Begriffe entscheidbar, berechenbar
und rekursiv gleichwertig sein.
Zunächst nähern wir uns dieser Frage mit der Betrachtung der
Turing-Maschine.
Wir können folgende Fragestellungen formulieren, bzw. eine Turing-Maschine
damit beauftragen, folgende Probleme zu lösen:
-
Z.B.: Berechne die Wurzel aus a.
-
Z.B.: Ist a eine Primzahl?
Für die erste Aufgabenstellung erhält die TM als Eingabe die
z.B. unär codierte Zahl a, als Ausgabe soll nach der Berechnung die
Wurzel aus a auf dem Band stehen. Es stellt sich die Frage, ob diese Aufgabe
berechenbar
ist.
Letzterer Frage liegt ein Entscheidungsproblem zugrunde, d.h.
es ist eine Frage, die mit ja oder nein beantwortet werden kann oder sollte.
Ein Entscheidungsproblem kann als Funktion mit dem Bildbereich {0,1}
aufgefaßt werden (Charakteristische Funktion).
Eine entsprechende TM liefert bei positiver Antwort die Ausgabe 1 (an
der Stelle des Bandes, wo der Schreib-/Lesekopf beim Halten steht), sonst
0, sofern das Problem überhaupt berechenbar ist.
Eine Sprache L und ein Entscheidungsproblem gehören eng zusammen:
-
Zu einer Sprache L gehört das Entscheidungsproblem, zu entscheiden,
ob ein Wort in L ist.
-
Zu einem Entscheidungsproblem gehört die Sprache L aller Zeichenketten,
für die das Entscheidungsproblem positiv ausfällt (die TM akzeptiert
oder die Charakteristische Funktion 1 ist).
DEFINITIONEN:
-
Eine Sprache L heißt rekursiv (entscheidbar)
gdw.
es eine TM gibt,
-
die auf allen Eingaben hält
-
und ein Wort genau dann akzeptiert, wenn es aus L ist.
-
Eine Sprache L heißt rekursiv-aufzählbar (semientscheidbar)
gdw.
es eine TM gibt,
-
die genau die Eingaben aus L akzeptiert.
-
(auf Eingaben, die nicht aus L sind, muß die TM nicht notwendiger
Weise halten.)
These von Church und Turing:
Die Klasse der Turing-Maschinen-berechenbaren Funktionen ist genau die
Klasse der "intuitiv" berechenbaren Funktionen.
Dies wird immer eine These bleiben, da der Begriff "intuitiv berechenbar"
nicht genau definiert ist. Die These sagt aber aus, daß Turingmaschinen
bereits alles berechnen können, was nach unserer Vorstellung berechenbar
ist.
Auch erweiterete Turingmaschinen wie solche mit mehreren Bändern
können nicht mehr berechnen als normale Turingmaschinen, wie man im
Einzelfall beweisen kann.
Abschlußeigenschaften rekursiver und rekursiv aufzählbarer Sprachen
Komplement, Vereinigung und Schnitt rekursiver Sprachen sind rekursiv.
Vereinigung und Schnitt rekursiv-aufzählbarer Sprachen sind
rekursiv-aufzählbar.
Wichtiger Satz:
Gegeben eine Sprache L, dann gilt:
(L rekursiv-aufzählbar UND Komplement von L rekursiv-aufzählbar)
<=> L entscheidbar
Frage:
Sind die rekursiv-aufzählbaren Sprachen gegen Komplementbildung
abgeschlossen?
Antwort:
NEIN, denn wären sie es, dann müßten sie nach obigem
Satz entscheidbar sein. Es gibt aber rekursiv-aufzählbare Sprachen,
die nicht rekursiv sind, wie wir noch sehen werden.