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


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