anzeigenwerbung.net

Gödelnummer

20.04.2012 @ 21:59, ʘx,

Eine Gödelnummer ist eine natürliche Zahl, die einem Wort einer formalen Sprache nach einem bestimmten Verfahren zugeordnet wird und dieses Wort eindeutig kennzeichnet. Ein solches Verfahren bezeichnet man als Gödelisierung. Alle über die Kodierung von Programmen in einer Programmiersprache definierten Aufzählungen sind Gödelnummerierungen. Die Bezeichnungen beziehen sich auf Kurt Gödel, der erstmals ein solches Verfahren angab, um seinen Unvollständigkeitssatz zu beweisen.

Formale Definition

Sei $M$ die (abzählbare) Menge der Wörter einer formalen Sprache. Eine Funktion
:$g:M\; \backslash to\; \backslash mathbb\{N\}$
wird Gödelisierung genannt, wennHans Hermes: Aufzählbarkeit – Entscheidbarkeit – Berechenbarkeit, 2. Auflage. Springer, Berlin 1971; S. 4. ISBN 3-540-05334-4, ISBN 0-387-05334-4
*$g$ injektiv und berechenbar,
*die Bildmenge $g(M)$ entscheidbar sowie
*die auf $g(M)$ definierte Umkehrfunktion von $g$ berechenbar ist.

$g(m)$ nennt man dann die Gödelnummer von $m$.

Beispiel

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

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,\backslash 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\backslash cdot9\backslash cdot\; 125\backslash cdot\; 343\backslash cdot\; 121\backslash cdot\; 13\; =\; 1\backslash ,213\backslash ,962\backslash ,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\backslash cdot\; 3^1$ (kein erster Buchstabe) oder $16\; =\; 2^4$ (Alphabet $\backslash 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.

Eine im Buch Gödel, Escher, Bach 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.

Gödelisierung von zahlentheoretischen Aussagen

Aussagen der Zahlentheorie (oder auch anderer mathematischer Theorien) lassen sich mit Hilfe eines endlichen Alphabets formulieren, dessen „Buchstaben“ neben Zeichen für Variablen auch gewisse mathematische und logische Symbole (etwa $+$, $\backslash cdot$, $=$, $\backslash and$, $\backslash Rightarrow$, $\backslash forall$) 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 $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$ durchnummeriert.
: $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 \#\backslash operatorname\{bin\}(m)\backslash \#\backslash operatorname\{bin\}(n)\backslash \#\backslash operatorname\{bin\}(m\text{'})\backslash \#\backslash operatorname\{bin\}(n\text{'})\backslash \#\backslash operatorname\{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 Eindeutigkeit der Primfaktorzerlegung aus, um Tupel in einer Zahl codieren zu können.

Siehe auch

* Church-Turing-These
* Gödelscher Unvollständigkeitssatz

* Turingmaschine

* Halteproblem

Einzelnachweis

{{DEFAULTSORT:Godelnummer}}

Kategorie:Berechenbarkeitstheorie

bn:গ্যোডেল সংখ্যা
ca:Nombre de Gödel
Gödel numbering
es:Numeración de Gödel
it:Numero di Gödel
ja:ゲーデル数
nl:Gödelnummer
pt:Número de Gödel
simple:Gödel number
sl:Gödlovo število
zh:哥德尔数
zh-yue:Gödel號數

weiter