Gödelnummer

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

Die Artikel Gödelnummer und Gödel-Isomorphismus überschneiden sich thematisch. Hilf mit, die Artikel besser voneinander abzugrenzen oder zu vereinigen. Die Diskussion über diese Überschneidungen findet hier statt. Bitte äußere dich dort, bevor du den Baustein entfernst. Agent00 ~ Diskussion 08:55, 22. Jan. 2007 (CET)

Eine Gödelnummer ist eine kodierte logische Aussage, welche 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.

Inhaltsverzeichnis

1 Formale Definition
2 Gödelisierung von Turingmaschinen
- 2.1 Beispiel
3 Siehe auch

[Bearbeiten] Formale Definition

Sei $M$ eine abzählbare Menge. Eine Funktion

$g:M \to \mathbb{N}$

wird Gödelisierung genannt, wenn $g$ sowie die inverse Funktion von $g$ berechenbar sind. $g (m)$ nennt man dann die Gödelnummer von $m$ .

[Bearbeiten] 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.

[Bearbeiten] 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, \Sigma, \Gamma, \delta, q_0, \square, F)$

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

$Q = \{q_0, q_1, \ldots, q_k\}, \Gamma= \{a_0, a_1, \ldots, a_l\}, k,l \in \mathbb{N}$

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

$\delta(q_m, a_n) = (q_m', a_n', \{L,N,R\}) \mapsto \#\#\operatorname{bin}(m)\#\operatorname{bin}(n)\#\operatorname{bin}(m')\#\operatorname{bin}(n')\#\operatorname{bin}(b)$

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

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

Die Turingmaschine mit der einzigen Produktion $\delta(q_0, 0) \mapsto (q_0, 0, N)$ wird so zu $10100010001000100010012 = 2656393 10$ .

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