BuK-Übung07
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.
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
Stream-Prozeduren
Prozeduren für Wortmengen-Stream
Prozeduren für Primzahlenverschlüsselung
Hauptprozedur
Die Hauptprozedur für die Gödel-Funktion ist nun mit den Hilfsfunktionen realisiert.
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.
Hilfsprozeduren
Hauptprozedur
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:
h(x) = G(f(G^{-1}(x)))- wenn h berechenbar ist:
f(x) = G^{-1}(h(G(x)))