BuK/IIm11/Studenten/simawiel/ue11

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
= Kreativaufgabe (Gödelisierung und $\mu$-rekursive Funktionen =

<code id="4fe09dee4fd56" hidden>
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; Hilfsfunktionen                                ;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define pow
  (lambda (number exp)
    (if (= exp 0)
      1
      (* number (pow number (- exp 1))))))

(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 create-word
  (lambda (alphabet word-number cardinal-number word-length)
    (if (= 0 word-length)
      ""
      (let ((section-size (pow cardinal-number (- word-length 1))))
        (let ((rest (modulo word-number section-size))
            (result (quotient word-number section-size)))
          (if (= 0 rest)
            (string-append
              (string (get-elem alphabet result))
              (create-word alphabet section-size cardinal-number (- word-length 1)))
            (string-append
              (string (get-elem alphabet (+ result 1)))
              (create-word alphabet rest cardinal-number (- word-length 1)))))))))

(define index-of
  (lambda (word alphabet)
      (if (equal? word (car alphabet))
      1
      (+ 1 (index-of word (cdr alphabet))))))

(define fill-with-indexes
  (lambda (word-as-list list-to-fill alphabet)
    (if (null? word-as-list)
      list-to-fill
      (let* ((index (index-of (car word-as-list) alphabet)) (temp-list (append list-to-fill (list index))))
        (fill-with-indexes (cdr word-as-list) temp-list alphabet)))))
    
(define goedel-product-sum
  (lambda (indexes zero-based-length)
    (cond
      ((= 0 zero-based-length) 1)
      (else (+ 
              (* (car indexes) (expt 3 zero-based-length))
              (goedel-product-sum (cdr indexes) (- zero-based-length 1)))))))
</code>

<code id="4fe09dee4fdc7">
(define S (list #\a #\b))

(define goedel 
  (lambda (word alphabet)
    (let ( (indexes (fill-with-indexes (string->list word) '() alphabet)) )
    (goedel-product-sum indexes (- (length indexes) 1)))))
</code>

<run id="4fe09dee4ff0e">
(display "Rufe Gödel-Funktion auf:")
(display "(goedel 'aba' S)\n")
(goedel "aba" S)
</run>

<code id="4fe09dee4fe31">
(define word-of-power-set?
  (lambda (goedel-number-for-word index word-length alphabet)
    (cond 
      ((> index (expt (length alphabet) word-length)) 
         (word-of-power-set? goedel-number-for-word 1 (+ word-length 1) alphabet))
      ((= (goedel (create-word alphabet index (length alphabet) word-length) alphabet) goedel-number-for-word)
         #t)
      ((> (goedel (create-word alphabet index (length alphabet) word-length) alphabet) goedel-number-for-word)
         #f)
      (else 
        (word-of-power-set? goedel-number-for-word (+ index 1) word-length alphabet)))))
   
(define goedel-number?
  (lambda (number alphabet)
    (word-of-power-set? number 1 1 alphabet)))
</code>

<run id="4fe09dee4ff6e">
(goedel-number? (goedel "abbbbbbaaabab" S) S)
</run>
<run id="4fe09e7763d55">
(goedel-number? 15 S)
</run>
== Das Prädikat p ==
<code id="4fe09dee4fe92">
(define p
  (lambda (r y)
    (if (and (<= r y) (goedel-number? y S)) 1 0)))
</code>

<run id="4fe09dee4ffca">
(p 12 15)
</run>
<run id="4fe09e7763dca">
(p 16 16)
</run>