Aus ProgrammingWiki

Gödelisierung

Aufgabe

Gegeben ist ein Alphabet , mit in der Verschlüsselung im 3er-System, mit und . Die Gödelisierungsfunktion von ist so definiert:

mit

Die Funktion ist ein total berechenbares Prädikat. Sie stelt für eine beliebige natürliche Zahl fest, ob diese eine Gödelnummer (des oben genannten Algorithmus) ist oder nicht.

Eine Funktion wächst streng monoton und ist total. Sie listet alle Gödelnummern für diesen Algorithmus auf.

Die Funktion ist die Umkehrfunktion von h und nimmt eine Gödelnummer und liefert ein Wort aus

Diese Funktionen sollen als Prozeduren in Scheme illustriert werden.

Lösung

(define myreverse (lambda (ls) (if (null? ls) ls (append (myreverse (cdr ls)) (list (car ls)))))) (define mystringreverse (lambda (str) (list->string (myreverse (string->list str))) )) (define wortmenge-stufe (lambda (n alphabet) (if (= n 0) '("") (apply append (map (lambda (zeichen) (map (lambda (wort)(string-append (string zeichen)wort)) (wortmenge-stufe (- n 1) alphabet))) alphabet))))) (define wortmenge-bis-stufe (lambda (n alphabet) (if (= n 0) (wortmenge-stufe 0 alphabet) (append (wortmenge-bis-stufe (- n 1) alphabet) (wortmenge-stufe n alphabet))))) (define S '("a" "b")) ;Alphabet (define Scode '(1 2)) ;Alphabet-Kodierung ;help procedures for h (define h_helper (lambda (w i) (list-ref Scode (get-i-te-Element_index (get-i-te-Element_content w i))) )) (define get-i-te-Element_content (lambda (str i) (string (list-ref (string->list str) i)) )) (define get-i-te-Element_index (lambda (str) (get-indices str S) )) ;get (OUT) i from (IN) element and list (define get-indices (lambda (letter liste) (define (loop rest-of-liste index) (if (null? rest-of-liste) 'exeption (let ((rest-of-indices (loop (cdr rest-of-liste) (+ index 1)))) (if (equal? (car rest-of-liste) letter) index rest-of-indices)))) (loop liste 0)))

Die Funktion rechent für ein gegebenes Wort den mathematischen Ausdruck aus.

(define h (lambda (w) (define sum 0) ;SUM{i=0}{|w|-1}{ai * 3^i} (do ((i 0 (+ i 1))) ((> i (- (length (string->list w)) 1))) (set! sum (+ sum (* (h_helper w i) (expt (+ 1 (length S)) i)))) ) sum ))

(h "aba")

ausführen

Das Prädikat prüft ob quasi ob die gegebene Zahl mit dieser Bildsungsvorschrift erzeugt werden kann oder nicht.

(define p (lambda (y) (if (gödelnr? y) 1 0) )) (define gödelnr? (lambda (y) (if (= 0 y) #t (if (= 0 (modulo y (+ 1 (length S)))) #f (gödelnr? (floor (/ y (+ 1 (length S)))))) ) ))

Die Zahl ist im Gegensatz zur eine Gödelnummer. Beide Aufrufe liefert , da diese mit dem Erwarteten Wert getestet werden.

(equal? (gödelnr? 16) #t) (equal? (gödelnr? 15) #f)

ausführen

Mit dieser Prädikatsfunktion ist es ein leichtes die Funktion für die Auflistung zu schreiben. Man geht alle natürlichen Zahlen bis zu einem Maximum durch und immer wenn diese Zahl eine Gödelnummer ist, dann wird sie zu einer Liste hinzufgefügt.

(define g (lambda (max) (g_helper 1 max '()) )) (define g_helper (lambda (i max liste) (if (< (length liste) max) (and (if (gödelnr? i) (g_helper (+ i 1) max (append liste (list i))) (g_helper (+ i 1) max liste))) liste) ))

(g 100)

ausführen

Für Funktion wird die Berechenbarkeit der Funktion und die Aufzählbarkeit des

Alphabets ausgenutzt. Genau diese beiden Mengen werden aufgezählt und sind gleichmächtig.

Der Algorithmus arbeitet so:

1. Auflistung aller Gödelnummern (Funktion g)
2. Der Indizes der passenden Gödelnummer wird gesucht und immer gefunden, falls Gödelnummer existiert
3. Eine Liste, in der aufgezählt wird, wird erzeugt.
4. Aus dieser Liste, wird anhandes des gefundenen Indezes das Wort herausgenommen.
5. Da "rückwärts" arbeitet, muss noch das Reverse genommen werden.

(define k (lambda (n) (mystringreverse (list-ref (f) (+ (get-indices n (g n)) 0))) )) (define f (lambda () (cdr (wortmenge-bis-stufe 7 (string->list "ab")));5 = Stufe ))

Folgende verschachtelteAufrufe sollen die Eigenschaft dass ist, durch Tests demonstrieren.

(= (h (k (h "aba"))) (h (k 16))) (= (h (k (h "aabbba"))) (h (k 481)))

ausführen