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