BuK/IIm11/Studenten/sirabien/goedelisierung

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
=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=
<code id="4fe090ebc6161">;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))</code>

=Gödelisierung=

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

<code id="4fe090ebc61d9">(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))))))))</code>

<run id="4fe090ebc6502">(display "Gödelnummer von abab:\n")
(h "abab")</run>

=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}}$

<code id="4fe090ebc6265">;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)))))))))</code>
<run id="4fe090ebc6567">(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)</run>

=G=
Die Prädikatsfuntion für g
<code id="4fe090ebc62ec">(define p
  (lambda (r y)
    (if (> r y)
      0
      (if (equal? #f (nice-h-1 y))
	0
	1))))</code>

Die Funktion g errechnet die n-te gültige Gödelnummer wobei n als Parameter übergeben wird.
<code id="4fe090ebc6390">(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))))</code>
<run id="4fe090ebc65cb">(display "Die 8. Gödelnummer ist:\n")
(g 8)</run>

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.

<code id="4fe090ebc6402">(define goedelGen
  (lambda (n)
    (if (= n 0)
      '()
      (append (goedelGen (- n 1)) (list (g n))))))</code>
<run id="4fe090ebc662a">(display "Die ersten 8 Gödelnummern sind:\n")
(goedelGen 8)</run>

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

<code id="4fe090ebc646f">(define k
  (lambda (n)
    (nice-h-1 (g n))))</code>
<run id="4fe090ebc668c">(display "Das 8. Wort der gödelgeordneten Folge der Wörter aus S* ist:\n")
(k 8)</run>