Diagonalsprache

Dieser Artikel oder nachfolgende Abschnitt ist nicht hinreichend mit Belegen (beispielsweise Einzelnachweisen) ausgestattet. Angaben ohne ausreichenden Beleg könnten demnächst entfernt werden. Bitte hilf Wikipedia, indem du die Angaben recherchierst und gute Belege einfügst.

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. Das heißt, es gibt keine Turingmaschine, die eine klare Ja-Nein-Antwort auf die Frage liefert, ob ein Wort zu der Sprache gehört oder nicht. Eine Turingmaschine kann zwar für Wörter aus der Sprache bestätigen, dass sie tatsächlich darin enthalten sind, falls sie jedoch nicht enthalten sind, terminiert die Turingmaschine nicht.

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.

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}}\}}$

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 ${\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.