BuK/IIm11/BuK-Übung07

Wiki-Quelltext dieser Seite.

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

Eine Abbildung $G : A^* \rightarrow \N$ heißt <b>Gödelisierung von </b>$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. (<b>Übungsaufgabe: </b>(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.

<b>Beweis</b> 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.

-----

[[File:Goedelisierung_01_sifenits.png|Darstellung]]

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