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….
** diese lasse ich mir generieren
* zu jedem n kann durch (3) festgestellt werden, ob n Gödelnummer ist
** Wenn ja, muss nun das Wort aus A* für das jeweilige n bestimmt 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 durch (2) die Gödelnummer
** Das wird so lange gemacht, bis 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