BuK/IIm11/Studenten/sifenits

Wiki-Quelltext dieser Seite.

* präfix: BuK/IIm11/Studenten/sifenits


[[BuK/IIm11/Studenten/sifenits/Übung01|Übung 01]]
[[BuK/IIm11/Studenten/sifenits/Übung04|Übung 04]]



== 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|500px|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)))$