Eigenschaften der Gödelisierung (Stefan Scheumann, Ronald Krause, Tobias Salzmann, Robert Rosenberger)

Eine Abbildung G : A^* \rightarrow \N heißt Gödelisierung von A^*, wenn die folgenden Bedingungen erfüllt sind:

(1) G ist injektiv, d.h. für alle w, w'\in A^* gilt: Wenn w \neq w', dann G(w) \neq G(w^')

(2) G ist berechenbar, d.h. zu jedem Wort w \in A^* lässt sich G(w) in endlich vielen Schritten berechnen.

(3) G(A^*) ist entscheidbar, d.h. für jedes n \in \N lässt sich in endlich vielen Schritten feststellen, ob n \in G(A^*) gilt oder nicht.

(4) Die Umkehrfunktion G^{-1} : G(A^*) \rightarrow A^* ist berechenbar, d.h. zu jedem n \in G(A^*) lässt sich das Wort w mit G(w) = n in endlich vielen Schritten auffinden. (Übungsaufgabe: (4) folgt aus (1)-(3).)

Zu Zeigen: G^{-1} : G(A^*) \rightarrow A^* ist berechenbar.

Hierfür werden die ersten drei Eigenschaften der Gödelisierung benötigt:

Da G injektiv ist, lässt sich eine Aufzählprozedur angeben, welche jedes Wort aus A* aufzählt, dass heißt Wörter welche zu G(A^*) gehören oder nicht.

Da G berechenbar ist, kann eine Prozedur angegeben werden, welche die entsprechende Gödelnummer liefert.

Da G(A^*) auch entscheidbar ist, lässt sich genau bestimmen, ob ein Wort aus A^* zu G(A^*) gehört oder nicht.

Da G(A^*) berechenbar ist, kann durch das Ausführen von G(A^*), die zurückgebene Gödelunumer, mit der von G^{-1} verglichen werden.

Da G(A^*) ebenfalls entscheidbar ist und jedes Wort aus A^* durch G(A^*) aufgezählt wird, kann durch die Umkehrfunktion genau entschieden werden, ob ein Wort aus A^* für die Gödelnummer existiert oder nicht.

Primzahlverschlüsselung (Ingo Körner, Christof Ochmann, Raik Bieniek, Max Wielsch)

Schreiben Sie Prozeduren für G (Primzahlverschlüsselung) und G^{−1}:G(A^∗)→A^∗. Erzeugen Sie auch den Stream für A^∗ bei gegebenem Alphabet A unter Verwendung der Primzahlverschlüsselung als Gödelisierung. Dokumentieren Sie die Verwendung der Prozeduren im ProgrammingWiki.

Gödelisierung

Die Gödelisierung bezeichnet das Verfahren, ein Wort aus einer Wortmenge (A^*) auf die Menge der Zahlen abzubilden. Dadurch sind Probleme der "Wort-Welt", also Probleme, die mit Programmiersprachen beschrieben werden können, ebenso in der Zahlenwelt (Mathematik) darstellbar und lösbar.

Hilfsprozeduren

Zunächst werden für die Realisierung der Gödelfunktion einige Hilfsprozeduren benötigt, die die Teiloperationen der Primzahlenverschlüsselung kapseln.

Hauptprozedur

Die Hauptprozedur für die Gödel-Funktion ist nun mit den Hilfsfunktionen realisiert.

Der Aufruf der Gödel-Funktion mit dem Wort aac liefert das Ergebnis 750. Diese Zahl ist die Gödelnummer dieses Wortes.

Umkehrung der Gödelisierung

Für die "Ent-Gödelisierung" muss nun aus einer Gödelnummer ein Wort aus der Wortmenge (Das Urbild der Abbildung) erzeugt werden, das mit der Gödel-Funktion benutzt wieder genau dieselbe Gödelnummer ergibt.

Prinzip der Gödelisierung (Daniel Tasche, Jens Heider, Felix Nitsche, Stefan Lüttke)

f : G(A^*) \rightarrow G(A^*) und h : A^* \rightarrow A^* sind Funktionen. f ist eine berechenbare Funktion genau dann, wenn h eine berechenbare Funktion ist.

Beweis als Übungsaufgabe: argumentativ für h = G^{-1} \circ f \circ G und f = G \circ h \circ G^{-1} unter Bezugnahme auf das Prinzip der Gödelisierung.

Da G und G^{-1} berechenbar sind, lassen sich f(x) oder h(x) mit den jeweils verbleibenden Funktionen ausdrücken.

- wenn f berechenbar ist:

- wenn h berechenbar ist: