goedelisierung

Aus ProgrammingWiki

Inhaltsverzeichnis

1 Aufgabe
2 Hilfsfunktionen
3 Gödelisierung
4 Umkehrfunktion der Gödelisierung
5 G

Aufgabe

Illustrieren Sie die folgenden Aussagen durch den Einsatz selbst entwickelter Scheme-Prozeduren. Wählen Sie exemplarisch S = {a, b} und die Verschlüselung im 3er-System, mit a \mapsto 1, b \mapsto 2 als Gödelisierung h mit h(w) = \sum_{i=0}^{|w|−1}~{a_i3^i} mit a_i ∈ \{1, 2\}. Das Wort aba erhält dann die Gödelnummer h(aba) = 1 \cdot 32 + 2 \cdot 31 + 1 \cdot 30 = 16.

Nicht jede natürliche Zahl ist Gödelnummer eines Wortes aus S^∗: Beispielsweise ist 10 = 1 \cdot 32 + 0 \cdot 31 + 1 \cdot 30 keine.

Hilfsfunktionen

;Returns the position of an element in a list (first element has position 1).
(define position
  (lambda (element list)
    (if (null? list)
      (position element list) ;(rotate #\T 180)
      (if (equal? element (car list))
	1
	(+ 1 (position element (cdr list)))))))

;Returns the element at the position in a list (first element has position 1).
(define element
  (lambda (position list)
    (if (null? list)
      (element position list) ;(rotate #\T 180)
      (if (= position 1)
	(car list)
	(element (- position 1) (cdr list))))))

(define BASE 3)
(define S '(#\a #\b))

Gödelisierung

Die Scheme Prozedur zur Gödelisierung von S^* durch Verschlüsselung im 3er-System.

(define h
  (lambda (w)
    (let* (
	(wList (string->list w))
	(letterCount (length wList)))
      (if (= letterCount 0)
	0
	(+
	  (* (position (car wList) S) (expt BASE (- letterCount 1)))
	  (h (list->string (cdr wList))))))))

(display "Gödelnummer von abab:\n")
(h "abab")

Umkehrfunktion der Gödelisierung

Die Umkehrfunktion h^-1 liefert für Nicht-Gödelnummern kein Ergebnis. Sie würde also ewig weiter laufen. Um eine Funktion zu erhalten, die für später für die Prädikatsfunktion verwendet werden kann, ist im folgende Funktion implementiert:

nice\text{-}h^{-1}(x) = =\cases{h^{-1}(x), \text{wenn x Gödelnummer}\\ false, \text{sonst}}

;Returns the word for the Gödelnumber n if n is a Gödelnumber or
;false if it's not.
(define nice-h-1
  (lambda (n)
    (let (
	(quot (quotient n BASE))
	(rest (modulo n BASE)))
      (if (= rest 0)
	#f
	(let ((letter (string (element rest S))))
	  (if (= quot 0)
	    letter
	    (let ((word (nice-h-1 quot)))
	      (if (equal? word #f)
		#f
		(string-append word letter)))))))))

(display "Wort für Gödelnummer 50:\n")
(nice-h-1 50)
(display "Ergebnis für Zahl die keine Gödelnummer ist:\n")
(nice-h-1 10)

G

Die Prädikatsfuntion für g

(define p
  (lambda (r y)
    (if (> r y)
      0
      (if (equal? #f (nice-h-1 y))
	0
	1))))

Die Funktion g errechnet die n-te gültige Gödelnummer wobei n als Parameter übergeben wird.

(define g
  (lambda (i)
    (letrec
	((fkt (if (= i 1)
	    (lambda (n)
	      (= 0 (- 1 (p 0 n))))
	    (lambda (n)
	      (= 0 (- 1 (p (+ (g (- i 1)) 1) n))))))
	(worker
	  (lambda (n)
	    (if (fkt n)
	      n
	      (worker (+ n 1))))))
      (worker 1))))

(display "Die 8. Gödelnummer ist:\n")
(g 8)

Die folgende Funktion gibt eine Liste mit den ersten n Gödelnummern zurück. Laut Hinweis sollen die ersten 10 Gödelnummern zurück gegeben werden. Das dauert allerdings zu lang.

(define goedelGen
  (lambda (n)
    (if (= n 0)
      '()
      (append (goedelGen (- n 1)) (list (g n))))))

(display "Die ersten 8 Gödelnummern sind:\n")
(goedelGen 8)

Die Funktion k gibt das Wort zurück, welches der n-ten Gödelnummer entspricht.

(define k
  (lambda (n)
    (nice-h-1 (g n))))

(display "Das 8. Wort der gödelgeordneten Folge der Wörter aus S* ist:\n")
(k 8)