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 die zu einer Kodierung gehörige Turingmaschine. Dann ist die Diagonalsprache definiert als:

D ist nicht semi-entscheidbar

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

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

  • Angenommen, :
    • müsste akzeptieren, denn semi-entscheidet .
    • Nach Definition von ist damit aber .
    • Widerspruch
  • Angenommen, :
    • darf nicht akzeptieren, denn semi-entscheidet .
    • Wiederum nach Definition von ist damit aber .
    • Widerspruch

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

Das Komplement von D ist semi-entscheidbar

Das Komplement von , das sogenannte spezielle Halteproblem, ist jedoch semi-entscheidbar. Definieren wir dieses als , so akzeptiert folgende Turingmaschine die Menge :

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

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

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