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.

Die Konstruktion der Sprache basiert auf dem Prinzip der Diagonalisierung. Die Diagonalsprache ist die Menge aller Turingmaschinen, die nicht akzeptieren, 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 ${\displaystyle M_{w}}$ die zu einer Kodierung ${\displaystyle w}$ gehörige Turingmaschine. Dann ist die Diagonalsprache ${\displaystyle D}$ definiert als: ${\displaystyle 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 ${\displaystyle D}$ semi-entscheidbar wäre, gäbe es eine Turingmaschine ${\displaystyle M}$, die ${\displaystyle D}$ semi-entscheidet, so dass alle Elemente ${\displaystyle x\in D}$ von ${\displaystyle M}$ akzeptiert werden, und für Elemente ${\displaystyle x\notin D}$ ${\displaystyle M}$ hält ohne zu akzeptieren oder nicht hält. Sei ${\displaystyle w}$ die Kodierung dieser Turingmaschine ${\displaystyle M}$, also ${\displaystyle M=M_{w}}$. Wenn ${\displaystyle M_{w}}$ mit Eingabe ${\displaystyle w}$ gestartet wird (also ihre eigene Kodierung entscheiden soll), gibt es folgende Möglichkeiten:

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

Somit kann es eine solche Turingmaschine ${\displaystyle M}$ nicht geben, die ${\displaystyle D}$ semi-entscheidet.

Das Komplement von D ist semi-entscheidbar

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

• Bei Eingabe ${\displaystyle w}$ wird ${\displaystyle M_{w}}$ bei Eingabe ${\displaystyle w}$ simuliert.
• Sobald ${\displaystyle M_{w}}$ in einer akzeptierenden Konfiguration hält, hält auch ${\displaystyle M}$ und akzeptiert.

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

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