Gödelnummer

Beispiel

Angenommen, beliebige Wörter der formalen Sprache $L$, die auf dem Alphabet $\Sigma$ basieren, sollen gödelisiert werden. Hier sei $\Sigma =\{a,b,c\}$.

Eine Möglichkeit der Kodierung wäre, den Buchstaben zunächst einfach fortlaufende Nummern zuzuweisen. Ein a entspräche der 1, ein b der 2 und ein c der 3. Nun kann man gödelisieren, indem man die dem Buchstaben entsprechenden Potenzen der fortlaufenden Primzahlen $2,3,5,7,\ldots$ miteinander multipliziert:

Das Wort abccba

• Das a an erster Stelle hat den Wert $2^{1}=2$
• Das b an zweiter Stelle hat den Wert $3^{2}=9$
• Das c an dritter Stelle hat den Wert $5^{3}=125$
• Das c an vierter Stelle hat den Wert $7^{3}=343$
• Das b an fünfter Stelle hat den Wert $11^{2}=121$
• Das a an sechster Stelle hat den Wert $13^{1}=13$

Die Gödelnummer für abccba in dieser Kodierung lautet also $2\cdot 9\cdot 125\cdot 343\cdot 121\cdot 13=1\,213\,962\,750$

Da es unendlich viele Primzahlen gibt, kann man auf diese Weise tatsächlich beliebig lange Wörter kodieren und aufgrund der Eindeutigkeit der Primfaktorzerlegung lässt sich etwa aus der Zahl 1213962750 wieder das Wort abccba rekonstruieren. Es gibt zwar Zahlen, die keinem Wort der Sprache entsprechen, beispielsweise $3=2^{0}\cdot 3^{1}$ (kein erster Buchstabe) oder $16=2^{4}$ (Alphabet $\Sigma$ hat kein viertes Element). Aber zumindest lassen sich diese ungültigen Werte auf berechenbare Weise von den gültigen unterscheiden.

Neben der hier gezeigten gibt es natürlich noch andere Methoden, eine Gödelisierung durchzuführen. Man könnte beispielsweise für die Nummerierung der Zeichen des Alphabets ebenfalls die Primzahlfolge verwenden. Das ist zwar grundsätzlich nicht nötig, erlaubt aber zusäzlich die Struktur von Termen (Formeln) mit zu kodieren.

Eine im Buch Gödel, Escher, Bach von Douglas Hofstatter beschriebene Methode verwendet beispielsweise ein Stellenwertsystem mit der Basis 1000, was zwar sehr anschaulich ist, aber formal schwieriger zu handhaben ist als eine Methode, die wie die obige auf Primzahlpotenzen beruht. Das gilt erst recht für die im IT-Bereich verwendeten Codierungen - etwa Unicode-Codierungen wie UTF-7, mit denen man auch die Sonderzeichen abbilden kann. Diese ordnen einer Zeichenkette (String) eine Folge von Hexadezimal- bzw. Binärziffern zu, die man als Ganzes als eine Gödelnummer auffassen kann (das Nullbyte bedeutet üblicherweise Ende des Darstellungsstrings, daher sollte es keine Eindeutigkeitsproblemen wegen führender Nullen geben - ansonsten kann eine binäre 1 vorangestellt werden). Die Rekonstruktion der Zeichenfolge aus dieser Zahlendarstellung ist aufgrund der geforderten technischen Funktionalität gegeben.