Sei eine Gödelisierung von , d.h. ist injektiv, total und berechenbar. ist entscheidbar und ist berechenbar.
Dann können die Wörter aus vermöge gödelgeordnet werden, so dass , für alle und .
Die folgende µ-rekursive Funktion liefert die Folge der Gödelnummern in aufsteigender Form.
Für gilt:
Die zur Definition von verwendete zahlentheoretische Funktion ist
Illustrieren Sie die folgenden Aussagen durch den Einsatz selbst entwickelter Scheme-
Prozeduren. Wählen Sie exemplarisch und die Verschlüsselung im 3er-System,
mit als Gödelisierung h mit mit . Das Wort
aba erhält dann die Gödelnummer . Nicht jede natürliche
Zahl ist Gödelnummer eines Wortes aus : Beispielsweise ist
keine.
ist ein total berechenbares Prädikat. (Hinweis: Hierzu benötigen Sie eine Scheme-Prozedur für ein total berechenbares Prädikat, das feststellt, ob eine gegebene Zahl y Gödelnummer ist, d.h. y muss in der Form mit darstellbar sein.)
wächst streng monoton und ist total. (Hinweis: Verwenden Sie eine Scheme-Prozedur zur Berechnung der ersten 10 Gödelnummern.)
Mit Hilfe der Funktion kann man das -te Wort in der gödelgeordneten Folge der Wörter aus bestimmen. ist total und injektiv. Die zugehörige Umkehrfunktion liefert somit auch wieder die Gödelisierung mit .
Lösung
Die Lösung für die Funktion lautet:
Die Umkehrung der Funktion , also , lautet:
Um heruaszufinden ob eine Zahl eine gültige Gödelnummer zu dem gegebenen System ist, kann die Funktion verwendet werden:
Lösung für Funktion
die zahlentheoretische Funktion , ist nur eine Erweiterung von h? mit der zusätzlichen Bedingung, dass y größer gleich r sein muss:
Funktion muss nicht extra implementiert werden, da diese aus (also hinvers) und besteht:
