Vorlesung7

Eigenschaften der Gödelisierung

z.z.: Aus (1), (2) und (3) folgt (4)

(1): Jedem Element aus natürlichen Zahlen wird höchstens ein Element aus A* zugeordnet (2) G(A*) ist berechenbar -> Es lässt sich eine Prozedur angeben, die G(w) in endlich vielen Schritten berechnet

(3) G(A*) ist entscheidbar -> Es lässt sich für jedes n von N in endlich vielen Schritten feststellen, ob n eine Gödelnummer ist

(4) es existiert eine berechenbare Umkehrfunktion zu allen Elementen in G(A*), um von

G(A*) zu A* zu kommen Herleitung von (4) Menge der natürlichen Zahlen ist aufzählbar -> 0,1,2,3…. lasse ich mir generieren zu jedem n kann mit (3) festgestellt werden, ob n Gödelnummer ist Wenn ja, muss nun das Wort aus A* für das jeweilige n herausgefunden werden A* ist ebenfalls aufzählbar -> längenlexigografische Ordnung aller Wörter möglich Wir bauen uns eine Generatorfunktion g für alle Wörter aus A* Lassen uns potentiell alle Wörter generieren Berechnen für jedes Wort mit (2) die Gödelnummer Das wird so lange gemacht, bin berechnete Gödelnummer mit unserem n übereinstimmt Dann haben wir für dieses n das Wort aus A* gefunden (Lösung erreicht) Durch (1) wird sichergestellt, dass für dieses n genau ein Wort aus A* existiert