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^*) \rightarrow A^*. Erzeugen Sie auch den Stream für A^* bei gegebenem Alphabet A unter Verwendung der Primzahlverschlüsselung als Godelisierung. Dokumentieren Sie die Verwendung der Prozeduren im ProgrammingWiki.

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: