Eine Gödelnummer ist ein kodiertes logisches Statement, welches für den Beweis des gödelschen Unvollständigkeitssatzes notwendig ist. Dabei wird für jede syntaktisch korrekte logische Aussage eine eindeutige Gödelnummer definiert. Alle über die Kodierung von Programmen in einer Programmiersprache definierten Aufzählungen sind daher Gödelnummerierungen.

Formale Definition

---

Eine Aufzählung $\backslash varphi\; \backslash in\; P^2\_1$ heißt Gödelnummerierung, wenn für alle $g\; \backslash in\; P^2\_1$ ein $h$ existiert, so dass $g\; =\; \backslash lambda\; i,x$ gilt. $h$ heißt dann Übersetzungsfunktion zu $g$ bezüglich $\backslash varphi$

Gödelisierung von Turingmaschinen

---

Eine bekannte Anwendung der Gödelnummer ist die Codierung einer Turingmaschine durch ein Binärwort $w$. Auf diese Weise wird jeder Turingmaschine eine Zahl zugeordnet (d. h. die Menge aller Turingmaschinen ist abzählbar). Diese Tatsache wird unter Anderem im Halteproblem ausgenutzt.

Beispiel

---

Natürlich lassen sich verschiedenste Konventionen für die Nummerierung vereinbaren. Im Folgenden soll der Vorgang an einem einfachen Beispiel gezeigt werden. Sei

$M\; =\; (Q,\; \backslash Sigma,\; \backslash Gamma,\; \backslash delta,\; q\_0,\; \backslash square,\; F)$

eine Turingmaschine. Seien o. B. d. A. die Zustandsmenge $Q$, sowie das Bandalphabet $\backslash Gamma$ durchnumeriert.

$Q\; =\; \backslash \{q\_0,\; q\_1,\; \backslash ldots,\; q\_k\backslash \},\; \backslash Gamma=\; \backslash \{a\_0,\; a\_1,\; \backslash ldots,\; a\_l\backslash \},\; k,l\; \backslash in\; \backslash mathbb\{N\}$

Wir codieren nun vorerst jeden Übergang $\backslash delta(q\_m,\; a\_n)\; =\; (q\_m\text{'},\; a\_n\text{'},\; \backslash \{L,N,R\backslash \})$ mit einem Wort über dem Alphabet $\backslash \{0,1,\backslash \#\backslash \}$. Zustände bzw. Terminalsymbole werden durch die Binärdarstellung ihrer Indizes dargestellt, die einzelnen Elemente werden mit $\backslash \#$ getrennt.

$\backslash delta(q\_m,\; a\_n)\; =\; (q\_m\text{'},\; a\_n\text{'},\; \backslash \{L,N,R\backslash \})\; \backslash mapsto\; \backslash \#\backslash \#bin(m)\backslash \#bin(n)\backslash \#bin(m\text{'})\backslash \#bin(n\text{'})\backslash \#bin(b)$

wobei $b$ die Kopfbewegung darstellt ($L\; =\; 0,\; N\; =\; 1,\; R\; =\; 2$). Um uns auf das zweistellige Alphabet $\backslash \{0,1\backslash \}$ beschränken zu können, führen wir eine Abbildung der Menge $\backslash \{0,1,\backslash \#\backslash \}$ auf $\backslash \{0,1\backslash \}$ ein:

$0\; \backslash mapsto\; 00,\; 1\; \backslash mapsto\; 01,\; \backslash \#\; \backslash mapsto\; 10$.

Die Turingmaschine mit der einzigen Produktion $\backslash delta(q\_0,\; 0)\; \backslash mapsto\; (q\_0,\; 0,\; N)$ wird so zu $1010001000100010001001\_2\; =\; 2656393\_\{10\}$.

Eine Alternative, die auf das Trennzeichen verzichtet, nutzt die Einzigartigkeit der Primzahlfaktorisierung aus, um Tupel in einer Zahl codieren zu können.

Siehe auch

---

• Church-Turing-These
• Gödelscher Unvollständigkeitssatz
• Gödel-Isomorphismus
• Turingmaschine
• Halteproblem

Berechenbarkeitstheorie

Gödel number | Gödlovo število | 哥德尔数