imported>AchimP: Lemma nur einmal fett, siehe WP:TYP

2026-04-15T14:53:44Z

Lemma nur einmal fett, siehe WP:TYP

Neue Seite

Eine '''Gödelnummer''' ist eine [[natürliche Zahl]], die einem [[Wort (Theoretische Informatik)|Wort]] einer [[Formale Sprache|formalen Sprache]] nach einem bestimmten Verfahren zugeordnet wird und dieses Wort [[Injektivität|eindeutig kennzeichnet]]. Ein solches Verfahren bezeichnet man als '''Gödelisierung'''. Die Bezeichnungen beziehen sich auf [[Kurt Gödel]], der erstmals ein solches Verfahren angab, um seinen [[Gödelscher Unvollständigkeitssatz|Unvollständigkeitssatz]] zu beweisen.

== Formale Definition ==

Sei <math>M</math> die ([[Abzählbarkeit|abzählbare]]) Menge der [[Wort (Theoretische Informatik)|Wörter]] <math>m</math> einer [[Formale Sprache|formalen Sprache]]. Eine [[Funktion (Mathematik)|Funktion]]
:<math>g\colon M \to \mathbb{N}</math>
wird ''Gödelisierung'' genannt, wenn<ref>Hans Hermes: ''Aufzählbarkeit – Entscheidbarkeit – Berechenbarkeit'', 2. Auflage. Springer, Berlin 1971; S. 4, ISBN 3-540-05334-4, ISBN 0-387-05334-4.</ref>
* <math>g</math> [[Injektivität|injektiv]] und [[Berechenbarkeit|berechenbar]],
* die [[Bild (Mathematik)|Bildmenge]] <math>g(M)</math> [[entscheidbar]] sowie
* die auf <math>g(M)</math> definierte [[Umkehrfunktion]] von <math>g</math> [[Berechenbarkeit|berechenbar]] ist.
<math>g(m)</math> nennt man dann die ''Gödelnummer'' von <math>m</math>.

== Beispiel ==
Angenommen, beliebige Wörter der [[Formale Sprache|formalen Sprache]] <math>L</math>, die auf dem [[Alphabet (Informatik) |Alphabet]] <math>\Sigma</math> basieren, sollen gödelisiert werden. Hier sei <math>\Sigma = \{a, b, c\}</math>.

Eine Möglichkeit der Kodierung ist, den Buchstaben zunächst einfach fortlaufende Nummern zuzuweisen, hier im Beispiel dem ''a'' die 1, dem ''b'' die 2 und dem ''c'' die 3. Nun kann man gödelisieren, indem man die dem Buchstaben entsprechenden Potenzen der fortlaufenden Primzahlen <math>2,3,5,7,\ldots</math> miteinander multipliziert:

Das Wort ''abccba''
* Das ''a'' an erster Stelle hat den Wert <math>2^1 = 2</math>
* Das ''b'' an zweiter Stelle hat den Wert <math>3^2 = 9</math>
* Das ''c'' an dritter Stelle hat den Wert <math>5^3 = 125</math>
* Das ''c'' an vierter Stelle hat den Wert <math>7^3 = 343</math>
* Das ''b'' an fünfter Stelle hat den Wert <math>11^2 = 121</math>
* Das ''a'' an sechster Stelle hat den Wert <math>13^1 = 13</math>
Die Gödelnummer für ''abccba'' in dieser Kodierung lautet also <math>2\cdot9\cdot 125\cdot 343\cdot 121\cdot 13 = 1\,213\,962\,750</math>

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 <math>3=2^0\cdot 3^1</math> (kein erster Buchstabe) oder <math>16 = 2^4</math> (Alphabet <math>\Sigma</math> 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 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ätzlich die Struktur von Termen (Formeln) mit zu kodieren.<ref>Vera Spillner: [https://www.spektrum.de/video/warum-goedels-unvollstaendigkeitssatz-mathematikern-ein-graus-ist/1507229#comment-1509095 Warum Gödels Unvollständigkeitssatz Mathematikern noch heute ein Graus ist], auf: Spektrum.de vom 2. Juli 2017, Leserbrief Nr. 3</ref>

Eine im Buch [[Gödel, Escher, Bach]] von [[Douglas R. Hofstadter|Douglas Hofstadter]] 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 [[Informationstechnik|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ärziffer]]n zu, die man als Ganzes als eine Gödelnummer auffassen kann (das Nullbyte bedeutet üblicherweise Ende des Darstellungsstrings, daher sollte es keine Eindeutigkeitsprobleme 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.

== Gödelisierung von zahlentheoretischen Aussagen ==
Aussagen der Zahlentheorie (oder auch anderer mathematischer Theorien) lassen sich mit Hilfe eines endlichen Alphabets formulieren, dessen Elemente neben Zeichen für Variablen auch gewisse mathematische und logische Symbole (etwa <math>+</math>, <math>\cdot</math>, <math>=</math>, <math>\land</math>, <math>\Rightarrow</math>, <math>\forall</math>) umfasst. (Die [[abzählbar unendlich]] vielen Variablen können als besonders gekennzeichnete Wörter des endlichen Alphabets dargestellt werden.)

Auf diese Weise lassen sich also zahlentheoretische Aussagen (und sogar Beweise) in Zahlen übersetzen.
Als Folge hiervon kann die Zahlentheorie, die ja Aussagen über Zahlen behandeln soll, auch Aussagen über zahlentheoretische Aussagen und Beweise behandeln.
Diese Tatsache ist der Punkt, an dem Gödels Unvollständigkeitssatz ansetzt.

== Gödelisierung von Turingmaschinen ==
Eine bekannte Anwendung der Gödelnummer ist die Kodierung einer [[Turingmaschine]] durch ein Binärwort <math>w</math>. Auf diese Weise wird jeder Turingmaschine eine natürliche Zahl zugeordnet (d. h. die Menge aller Turingmaschinen ist abzählbar). Diese Tatsache wird unter anderem im [[Halteproblem]] ausgenutzt.

=== Beispiel ===
Es lassen sich verschiedenste Konventionen für die Nummerierung vereinbaren. Im Folgenden soll der Vorgang an einem einfachen Beispiel gezeigt werden. Sei
: <math>M = (Q, \Sigma, \Gamma, \delta, q_0, \square, F)</math>
eine Turingmaschine.
Seien [[Ohne Beschränkung der Allgemeinheit|o. B. d. A.]] die Zustandsmenge <math>Q</math>, sowie das Bandalphabet <math>\Gamma</math> durchnummeriert.
: <math>Q = \{q_0, q_1, \ldots, q_k\}, \Gamma= \{a_0, a_1, \ldots, a_l\}; k,l \in \mathbb{N}</math>
Wir codieren nun vorerst jeden Übergang <math>\delta(q_m, a_n) = (q_{m'}, a_{n'}, b)</math> mit <math>b\in \{L,N,R\}</math>
durch ein Wort über dem Alphabet <math>\{0,1,\#\}</math>.
Zustände bzw. Terminalsymbole werden durch die Binärdarstellung ihrer Indizes dargestellt, die einzelnen Elemente werden mit <math>\#</math> getrennt.
: <math>\delta(q_m, a_n) = (q_{m'}, a_{n'}, b) \mapsto \#\#\operatorname{bin}(m)\#\operatorname{bin}(n)\#\operatorname{bin}(m')\#\operatorname{bin}(n')\#\operatorname{bin}(b)</math>
wobei <math>b</math> die Kopfbewegung darstellt (<math>L = 0, N = 1, R = 2</math>).
Um uns auf das zweistellige Alphabet <math>\{0,1\}</math> beschränken zu können, führen wir eine Abbildung der Menge <math>\{0,1,\#\}</math> auf <math>\{0,1\}</math> ein:
: <math>0 \mapsto 00, 1 \mapsto 01, \# \mapsto 10</math>.
Die Turingmaschine mit der einzigen Produktion <math>\delta(q_0, 0) \mapsto (q_0, 0, N)</math> wird so zu <math>1010001000100010001001_2 = 2656393_{10}</math>.

Eine Alternative, die auf das Trennzeichen verzichtet, nutzt die Eindeutigkeit der [[Primfaktorzerlegung]] aus, um Tupel in einer Zahl codieren zu können.

== Siehe auch ==
* [[Church-Turing-These]]

== Einzelnachweise ==
<references />

{{Normdaten|TYP=s|GND=1097779815}}

{{DEFAULTSORT:Godelnummer}}
[[Kategorie:Berechenbarkeitstheorie]]

Gödelnummer - Versionsgeschichte

imported>AchimP: Lemma nur einmal fett, siehe WP:TYP