Diagonalsprache

Die Diagonalsprache ist eine Formale Sprache aus der theoretischen Informatik aus dem Bereich der Entscheidungsprobleme. Sie ist als Menge so konstruiert, dass sie nicht semi-entscheidbar ist, also dass Elemente (Wörter) der Sprache nicht auf algorithmische Weise als zu der Sprache gehörig erkannt werden können. Es kann also keine Turingmaschine geben, die eine Ja-Antwort auf die Frage geben kann, ob ein Element zu der Sprache gehört.

Die Diagonalsprache ist die zentrale Konstruktion im Beweis der Unentscheidbarkeit des Halteproblems.

Einleitung

Die Konstruktion der Sprache basiert auf dem Prinzip der Diagonalisierung. Die Diagonalsprache ist die Menge aller Turingmaschinen, die nicht halten, wenn sie ihre eigene Kodierung als Eingabe bekommen. Eine Turingmaschine, welche diese Sprache semi-entscheiden könnte, dürfte weder in der Menge noch nicht in der Menge liegen, was zum Widerspruch zu angenommener Semi-Entscheidbarkeit führt.

Das Komplement der Diagonalsprache ist jedoch semi-entscheidbar. Es wird auch als das spezielle Halteproblem bezeichnet und ist das klassische Beispiel dafür, dass es semi-entscheidbare Sprachen gibt, die nicht entscheidbar sind, so dass die Klasse der entscheidbaren Sprachen eine echte Teilmenge der Klasse der semi-entscheidbaren Sprachen ist.

Definition

Sei M_w die zu einer Kodierung w gehörige Turingmaschine. Dann ist die Diagonalsprache D definiert als: $D := \{w \mid M_w ~\text{akzeptiert}~ w ~\text{nicht}\}$

D ist nicht semi-entscheidbar

Die Diagonalsprache ist nicht semi-entscheidbar, also ist sie auch nicht rekursiv aufzählbar.

Wenn D semi-entscheidbar wäre, gäbe es eine Turingmaschine M, die D semi-entscheidet, so dass alle Elemente $x \in D$ von M akzeptiert werden, und für Elemente $x \notin D$ M hält ohne zu akzeptieren oder nicht hält. Sei w die Kodierung dieser Turingmaschine M, also M = M_w. Wenn M_w mit Eingabe w gestartet wird (also ihre eigene Kodierung entscheiden soll), gibt es folgende Möglichkeiten:

• Angenommen, $w \in D$:
  • M_w müsste w akzeptieren, denn M_w semi-entscheidet D.
  • Nach Definition von D ist damit aber $w \notin D$.
  • Widerspruch
• Angenommen, $w \notin D$:
  • M_w darf w nicht akzeptieren, denn M_w semi-entscheidet D.
  • Wiederum nach Definition von D ist damit aber $w \in D$.
  • Widerspruch

Somit kann es eine solche Turingmaschine M nicht geben, die D semi-entscheidet.

Das Komplement von D ist semi-entscheidbar

Das Komplement von D, das sogenannte spezielle Halteproblem, ist jedoch semi-entscheidbar. Definieren wir dieses als $K := \{w \mid M_w ~\text{akzeptiert}~ w\}$, so akzeptiert folgende Turingmaschine M die Menge K:

• Bei Eingabe w wird M_w bei Eingabe w simuliert.
• Sobald M_w in einer akzeptierenden Konfiguration hält, hält auch M und akzeptiert.

Damit ist klar, dass jede Eingabe $w \in K$ genau dann von M akzeptiert wird, wenn M_w die Eingabe w akzeptiert. Für positive Eingaben, also $w \in K$, akzeptiert M die Eingabe. Für negative Eingaben, also $w \notin K$, hält M nicht in akzeptierender Konfiguration, hält also ohne in einen Endzustand zu gelangen oder hält gar nicht. Damit semi-entscheidet M die Sprache K.

Jedoch entscheidet M die Sprache K nicht, denn es kann negative Eingaben geben, auf denen die Turingmaschine nicht hält. Eine K entscheidende Turingmaschine kann es auch gar nicht geben, denn diese würde auch das Komplement von K (nämlich gerade die Diagonalsprache D) entscheiden, was nach obigen Ausführungen nicht sein kann.