BuK-KA-Goedelisierung und mu-rekursive Funktionen

Aus ProgrammingWiki

Kreativaufgabe: Gödelisierung und $\mu$-rekursive Funktionen

(define get-elem (lambda (set index) (if (= index 1) (car set) (get-elem (cdr set) (- index 1))))) ;Berechnet die Anzahl der Wörter mit Länge <= letterCount (define word-number (lambda (cardinal-number letter-count) (if (= letter-count 0) 0 (+ (pow cardinal-number letter-count) (word-number cardinal-number (- letter-count 1)))))) (define fCreator (lambda (set) (lambda (index) (if (= index 0) "" (let((cardinalNumber (cardinalNumber S)) (lettersRemaining (calculateWordSize S index))) (createWord S (- index (numberOfWords cardinalNumber (- lettersRemaining 1))) cardinalNumber lettersRemaining)))))) (define monus-minus (lambda (y) (if (<= 1 y) 0 (- 1 y)))) (define S '(#\a #\b)) (define cardinalNumber (lambda (set) (if (null? set) 0 (+ 1 (cardinalNumber (cdr set)))))) (define calculateWordSize (lambda (set index) (letrec ((calculateWordSizeReal (lambda (cardinalNumber index sum exp) (if (>= sum index) 0 (+ 1 (calculateWordSizeReal cardinalNumber index (+ sum (potenz cardinalNumber exp)) (+ 1 exp))))))) (calculateWordSizeReal (cardinalNumber set) index 0 1)))) (define createWord (lambda (set wordnumber cardinalNumber lettersRemaining) (if (= 0 lettersRemaining) "" (let ((sectionSize (potenz cardinalNumber (- lettersRemaining 1)))) (let ((rest (modulo wordnumber sectionSize)) (result (quotient wordnumber sectionSize))) (if (= 0 rest) (string-append (string (getElement set result)) (createWord set sectionSize cardinalNumber (- lettersRemaining 1))) (string-append (string (getElement set (+ result 1))) (createWord set rest cardinalNumber (- lettersRemaining 1))))))))) (define numberOfWords (lambda (cardinalNumber letterCount) (if (= letterCount 0) 0 (+ (potenz cardinalNumber letterCount) (numberOfWords cardinalNumber (- letterCount 1)))))) (define getElement (lambda (set index) (if (= index 1) (car set) (getElement (cdr set) (- index 1))))) (define potenz (lambda (zahl exponent) (if (= exponent 0) 1 (* zahl (potenz zahl (- exponent 1)))))) (define wort-laenge-eins (lambda (wort) (- (length wort) 1))) (define p (lambda (r y) (if (and (<= r y) (goedel-nummer? y)) 1 0))) (define f (fCreator S)) (define is-goedel? (lambda (y index) (cond [(eqv? (my-goedel(string->list(f index))) y) #t] [(>(my-goedel(string->list(f index))) y) #f ] [else (is-goedel? y (+ index 1))]))) (define goedel-nummer? (lambda (nr) (is-goedel? nr 1)))

(define S '(#\a #\b)) (define my-goedel (lambda (wort) (cond [(and (null? (cdr wort))(eqv? (car wort) #\a)) 1] [(and (null? (cdr wort))(eqv? (car wort)#\b)) 2] [(eqv? #\a (car wort)) (+ (my-goedel (cdr wort)) (* 1 (potenz 3 (wort-laenge-eins wort)))) ] [(eqv? #\b (car wort)) (+ (my-goedel (cdr wort)) (* 2 (potenz 3 (wort-laenge-eins wort)))) ] [else #f]))) (define h (lambda (wort) (my-goedel (string->list wort))))

Gödelisierung h (Verschlüsselung im 3-er System):

(h "aba")

ausführen

(define g (lambda (i m z) (cond [(equal? 0 z) (display "...") ] [(= (monus-minus (p i m)) 0) (display m)(display ", ") (g (+ m 1) 0 (- z 1)) ] [else (g i (+ m 1) z)]))) (define monus-minus (lambda (y) (if (<= 1 y) 0 (- 1 y)))) (define g-n-mal (lambda (n) (g 0 0 n)))

Die ersten n Gödelnummern:

(g-n-mal 15)

ausführen

(define is-goedel? (lambda (y index) (cond [(eqv? (my-goedel(string->list(f index))) y) #t] [(>(my-goedel(string->list(f index))) y) #f ] [else (is-goedel? y (+ index 1))]))) (define goedel-nummer? (lambda (nr) (is-goedel? nr 1)))

Prozedur goedel-nummer? prüft, ob es sich um eine gültige Gödelnummer handelt:

(goedel-nummer? (h "abba"))

ausführen

(goedel-nummer? 10)

ausführen

(define p (lambda (r y) (if (and (<= r y) (goedel-nummer? y)) 1 0)))

Scheme-Prozedur für ein total berechenbares Prädikat p:

(p 3 3)

ausführen

(p 3 4)

ausführen

(define f (fCreator S)) (define k (lambda (n) (f n)))

Prozedur k liefert das n-te Wort in der gödelgeordneten Folge der Wörter aus S*:

(h (k 10))

ausführen

(k 10)

ausführen