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).)

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.