BuK/IIm11/Studenten/sirabien/goedelisierung

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
=Hilfsfunktionen=
<code id="4fe090ebc6161">;Returns the position of an element in a list.
(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.
(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=
<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=
<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 "Ergebniss für Zahl die keine Gödelnummer ist:\n")
(nice-h-1 10)</run>

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

=G=
<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>

<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>

<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>