BuK/IIm18/Vorlesung7

Wiki-Quelltext dieser Seite.

== 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