ue7

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.

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.

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.