Wikipedia · einfach zusammengefasst · Stand
Diagonalsprache
Die Diagonalsprache ist die zentrale Konstruktion im Beweis der Unentscheidbarkeit des Halteproblems. Die Konstruktion der Sprache basiert auf dem Prinzip der …
Inhalt5 Abschnitte
Kernidee
Die Diagonalsprache ist eine formale Sprache aus der theoretischen Informatik, genauer aus dem Bereich der Entscheidungsprobleme. Sie ist wichtig, weil sie als zentrale Konstruktion im Beweis der Unentscheidbarkeit des Halteproblems dient.
Sie wird mit Diagonalisierung konstruiert. Dabei betrachtet man Turingmaschinen und ihre eigenen Kodierungen als Eingabe. Die Diagonalsprache enthält genau die Kodierungen solcher Turingmaschinen, die ihre eigene Kodierung nicht akzeptieren. Gerade diese Selbstbezüglichkeit führt zu einem Widerspruch, wenn man annimmt, die Sprache sei semi-entscheidbar.
Definition
Sei M_w die Turingmaschine, die zu einer Kodierung w gehört. Dann ist die Diagonalsprache D definiert als:
D := {w | M_w akzeptiert w nicht}
Das bedeutet: Ein Wort w gehört genau dann zu D, wenn die durch w kodierte Turingmaschine M_w bei Eingabe w nicht akzeptiert. „Semi-entscheidbar“ heißt hier: Es gäbe eine Turingmaschine, die alle Wörter der Sprache akzeptiert; bei Wörtern außerhalb der Sprache dürfte sie entweder halten, ohne zu akzeptieren, oder gar nicht halten.
Nicht semi-entscheidbar
Die Diagonalsprache D ist nicht semi-entscheidbar und damit auch nicht rekursiv aufzählbar.
Der Beweis läuft über einen Widerspruch. Angenommen, D wäre semi-entscheidbar. Dann gäbe es eine Turingmaschine M, die D semi-entscheidet: Für jedes x ∈ D akzeptiert M die Eingabe x; für jedes x ∉ D hält M ohne zu akzeptieren oder hält nicht. Sei w die Kodierung dieser Maschine M, also M = M_w.
Nun betrachtet man M_w mit der Eingabe w, also die Maschine auf ihrer eigenen Kodierung. Falls w ∈ D gilt, müsste M_w die Eingabe w akzeptieren, weil M_w ja D semi-entscheidet. Nach der Definition von D würde daraus aber folgen, dass w ∉ D ist. Das ist ein Widerspruch.
Falls umgekehrt w ∉ D gilt, darf M_w die Eingabe w nicht akzeptieren, weil M_w D semi-entscheidet. Nach der Definition von D folgt daraus aber, dass w ∈ D ist. Auch das ist ein Widerspruch. Also kann es keine Turingmaschine geben, die D semi-entscheidet.
Komplement und spezielles Halteproblem
Das Komplement von D ist semi-entscheidbar. Es wird als spezielles Halteproblem bezeichnet und ist definiert als:
K := {w | M_w akzeptiert w}
K enthält also genau die Kodierungen w, bei denen die durch w kodierte Turingmaschine M_w ihre eigene Kodierung w akzeptiert.
Eine Turingmaschine kann K semi-entscheiden, indem sie bei Eingabe w die Maschine M_w auf der Eingabe w simuliert. Sobald M_w in einer akzeptierenden Konfiguration hält, hält auch die simulierende Maschine und akzeptiert. Für positive Eingaben w ∈ K akzeptiert sie also genau dann, wenn M_w die Eingabe w akzeptiert. Für negative Eingaben w ∉ K hält sie nicht akzeptierend: Sie hält ohne akzeptierenden Endzustand oder hält gar nicht.
Bedeutung für Entscheidbarkeit
Das Beispiel zeigt den Unterschied zwischen entscheidbaren und semi-entscheidbaren Sprachen. K ist semi-entscheidbar, aber nicht entscheidbar. Eine entscheidende Turingmaschine müsste nämlich für jede Eingabe korrekt halten und entscheiden, ob sie in K liegt oder nicht.
Eine solche Maschine für K kann es nicht geben. Wenn K entscheidbar wäre, dann wäre auch sein Komplement entscheidbar. Das Komplement von K ist aber gerade die Diagonalsprache D. Da D nicht semi-entscheidbar ist und damit insbesondere nicht entscheidbar sein kann, ist auch K nicht entscheidbar. Deshalb ist die Klasse der entscheidbaren Sprachen eine echte Teilmenge der Klasse der semi-entscheidbaren Sprachen.
