BuK/IIm11/Studenten/sidatasc/ue7

Wiki-Quelltext dieser Seite.

== Gödelisierung ==

=== Prinzip der Gödelisierung ===

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

'''Lösung:'''

Laut den Bedinungen, die eine Gödelisierung vorraussetzt, sind $G$ und $G^{-1}$ berechenbar. Das Prinzip der Gödelisierung sagt aus, dass $h = G^{-1}  \circ f \circ G$. Daraus ergibt sich, dass $f = G \circ h \circ G^{-1}$. 

$G$ und $G^{-1}$ sind berechenbar (siehe Vorraussetzung 1 und 4). Das bedeutet nun, dass wenn $h$ nun ebenfalls berechenbar ist, auch $f$ berechenbar ist. Im Umkehrschluss folgt, dass wenn $h$ nicht berechenbar ist, auch $f$ nicht berechenbar ist.