Gödelnummer

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten (Unterschied zur vorletzten Version).

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.

[Bearbeiten] Formale Definition

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

[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 \#\#bin(m)\#bin(n)\#bin(m')\#bin(n')\#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.