goedelisierung

Aus ProgrammingWiki

Archivierte Version vom 2012-06-19T14:51:11+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Hilfsfunktionen
2 Gödelisierung
3 Umkehrfunktion der Gödelisierung
4 Prädidikat
5 G

Hilfsfunktionen

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

Gödelisierung

(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

;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 "Ergebniss für Zahl die keine Gödelnummer ist:\n")
(nice-h-1 10)

Prädidikat

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

G

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

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

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

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

goedelisierung

Inhaltsverzeichnis

Hilfsfunktionen

Gödelisierung

Umkehrfunktion der Gödelisierung

Prädidikat

G

Suche