• Home
• Theorie
  • Potenzmenge
  • Unendlichkeit der Primzahlen
  • Euler-Formel
  • Diagonalsprache
  • O-Kalkül
  • wp-Kalkül
  • Informationstheorie
  • Schnelle Fourier Transformation
  • Diskrete Kosinus Transformation
• Praxis
  • Huffman Kodierung
  • Primzahlen TM
• Aufschriebe
  • Papers
  • Mathematik
• Tutorien
  • Info III WS05/06
  • Info IV SS06
  • Info III WS06/07
  • Info IV SS07

Unentscheidbarkeit der Diagonalsprache

In der theoretischen Informatik betrachtet man häufig formale Sprachen. Eine formale Sprache ist im Grunde nichts weiter als eine (abzählbare) Menge von Wörtern über einem endlichen Alphabet $\Sigma$. Ist also $\Sigma^*$ die Menge aller Wörter, die man über $\Sigma$ bilden kann, so ist eine formale Sprache $L \subseteq \Sigma^*$ eine Teilmenge von $\Sigma^*$.

Die Frage ob eine formale Sprache $L$ (semi-)entscheidbar ist, ist die Frage danach, ob es eine Turingmaschine $\mathcal{T}$ gibt, die für alle Wörter $w \in L$ akzeptiert (also in einem akzeptierenden Endzustand hält), und alle Wörter $w \notin L$ ablehnt (also nicht in einen akzeptierenden Zustand gelangt). Für die Entscheidbarkeit verlangen wir noch strikter, dass die Turingmaschine immer hält, also auch für Wörter $w \notin L$ (natürlich in dem Fall in einem nicht-Endzustand).

Die Diagonalsprache

Die Diagonalsprache $L_d$ ist eine eher theoretisch konstruierte Sprache, für die man sehr elegant zeigen kann, dass sie nicht entscheidbar ist. Es gibt also keine Turingmaschine, die selbst für die Wörter $w \in L_d$ immer hält.

Da Turingmaschinen endliche Modelle sind, und sich somit durch endlich viele Symbole beschreiben lassen, kann man eine Turingmaschine $\mathcal{T}$ über dem Alphabet $\Sigma := \{0,1\}$ kodieren (Gödelnummerierung). Die Gödelnummer einer Turingmaschine $\mathcal{T}$ sei mit $\langle \mathcal{T} \rangle$ bezeichnet. Da die Gödelnummern Wörter über $\{0,1\}$ sind, können wir natürlich auch die umgekehrte Richtung einschlagen. Wir betrachten ein Wort $w \in \{0,1\}^*$, und fragen uns welche Turingmaschine durch dieses Wort kodiert wird. Es ist offensichtlich, dass es viele Wörter geben wird, die keinen sinnvollen Gödelkode darstellen, und damit eigentlich keine Turingmaschine definieren. Wir wollen für diese Wörter vereinbaren, dass sie die Turingmaschine beschreiben, die nichts (also die leere Sprache $\emptyset$) akzeptiert.

Um ein wenig System einzubringen, wollen wir die Wörter über $\{0,1\}$ in kanonischer Reihenfolge ordnen. Wir sagen $i < j$ für $w_i,w_j \in \{0,1\}^*$, falls $|w_i| < |w_j|$ oder, im Falle dass $|w_i| = |w_j|$, soll $w_i$ lexikographisch vor $w_j$ stehen. Mit Hilfe dieser Ordnung können wir ab jetzt vom $i$-ten Wort $w_i$ aus $\{0,1\}^*$ sprechen.

Nun wird es etwas haarig. Wir betrachten zum Wort $w_i$ die Turingmaschine $\mathcal{T}_i$, die durch die Gödelnummer $w_i$ beschrieben wird. Es ist also $\langle \mathcal{T}_i \rangle = w_i$. Wir konstruieren uns eine (unendlich große) Tabelle mit den Einträgen „ja“ und „nein“ wie folgt:

$$(i,j) := \left\{ \begin{array}{lc} \text{ja} & \text{falls $\mathcal{T}_j$ das Wort $w_i$ akzeptiert} \\ \text{nein} & \text{sonst} \end{array}\right.$$

Anschaulich bedeutet das, dass der Eintrag an der Stelle $(i,j)$ genau dann ein „ja“ enthält, wenn die Turingmaschine $\mathcal{T}_j$ (die durch das $j$-te Wort (gödel-)beschrieben wird), bei Eingabe des $i$-ten Wortes akzeptiert.

Die Diagonalsprache enthält nun genau die Wörter $w_i$, bei denen auf der Diagonalen, also im Eintrag $(i,i)$ ein „nein“ steht. Formal:

$$L_d := \{ w_i \;|\; \text{$\mathcal{T}_i$ akzeptiert bei Eingabe $w_i$ \text{nicht}} \}$$

Wir können uns fragen ob diese Sprache entscheidbar ist!

Die Unentscheidbarkeit

Die Sprache ist unentscheidbar, und wir führen Beweis durch Widerspruch.

Nehmen wir also an, die Sprache wäre entscheidbar. Dann muss es eine Turingmaschine geben, die $L_d$ entscheidet. Ferner lässt sich diese Turingmaschine gödelkodieren, so dass es ein Wort über dem Alphabet $\{0,1\}$ geben muss, das die Gödelnummer dieser Maschine ist. Mit Hilfe unserer Ordnung können wir sagen, dass diese Turingmaschine, nennen wir sie $\mathcal{M}_i$, durch das Wort $w_i$ kodiert wird.

Was passiert, wenn wir jetzt $\mathcal{M}_i$ mit der Eingabe $w_i$ (also sich selbst!) laufen lassen? Da wir annehmen, dass $\mathcal{M}_i$ die Diagonalsprache entscheiden kann, muss $\mathcal{M}_i$ das Wort entweder akzeptieren, woraus $w_i \in L_d$ folgt, oder ablehnen, was $w_i \notin L_d$ bedeutet.

• Nehmen wir an es ist $w_i \in L_d$, also $\mathcal{M}_i$ akzeptiert $w_i$. Dies führt uns aber direkt auf einen Widerspruch zur Definition der Diagonalsprache, denn $L_d$ enthält ja gerade die Wörter $w_i$, die von der entsprechenden Turingmaschine $\mathcal{T}_i$ (in unserem Fall ist das $\mathcal{M}_i$) nicht akzeptiert werden.
• Nehmen wir also an, es ist $w_i \notin L_d$. $\mathcal{M}_i$ lehnt das Wort $w_i$ somit ab. Mit der gleichen Argumentation führt das wieder auf einen Widerspruch zur Definition von $L_d$, denn würde $\mathcal{M}_i$ das Wort $w_i$ ablehnen, so muss es in $L_d$ vorhanden sein!

Es folgt mit dem Prinzip des Beweises durch Widerspruch, dass unsere Annahme nicht haltbar ist: $L_d$ ist also unentscheidbar. $\square$