sifenits
Aus ProgrammingWiki
- präfix: BuK/IIm11/Studenten/sifenits
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:
h(x) = G(f(G^{-1}(x)))- wenn h berechenbar ist:
f(x) = G^{-1}(h(G(x)))