BuK/IIm11/Studenten/simawiel/ue7

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
Schreiben Sie Prozeduren für G (Primzahlverschlüsselung) und $G^{−1}$:$G(A^∗)→A^∗$. Erzeugen Sie auch den Stream für $A^∗$ bei gegebenem Alphabet A unter Verwendung der Primzahlverschlüsselung als Gödelisierung. Dokumentieren Sie die Verwendung der Prozeduren im ProgrammingWiki.

= Gödelisierung =
Die Gödelisierung bezeichnet das Verfahren, ein Wort aus einer Wortmenge ($A^*$) auf die Menge der Zahlen abzubilden. Dadurch sind Probleme der "Wort-Welt", also Probleme, die mit Programmiersprachen beschrieben werden können, ebenso in der Zahlenwelt (Mathematik) darstellbar und lösbar.
== Hilfsprozeduren ==

Zunächst werden für die Realisierung der Gödelfunktion einige Hilfsprozeduren benötigt, die die Teiloperationen der Primzahlenverschlüsselung kapseln.
<code id="4fb295a00807c">
(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 devides?
  (lambda (a b)
    (= (modulo b a) 0 )))

(define find−denominator
  (lambda (a n)
    ;teile n durch a, wobei 2 < a < sqrt(n)
    (cond ((> (sqrt a) n) n)
          ((devides? a n) a)
          (else (find−denominator (+ a 1) n)))))

(define least-common-denominator
  (lambda (n) 
    ;finde a sodas gilt: a^n mod n = a
    (find−denominator 2 n)))

(define prime?
  (lambda (n)
    (= (least-common-denominator n) n)))

(define n->prime
  (lambda (n)
    (if (prime? n)
      n
      (n->prime (+ n 1)))))

(define next-prime
  (lambda (prime-number)
    (n->prime (+ prime-number 1))))

(define fill-with-primes
  (lambda (last-prime list-length list-to-fill)
    (if (= (length list-to-fill) list-length)
      list-to-fill
      (let ((np (next-prime last-prime)))
        (begin 
        (let ((temp-list (append list-to-fill (list np))))
        (fill-with-primes np list-length temp-list)))))))
</code>

== Hauptprozedur ==
Die Hauptprozedur für die Gödel-Funktion ist nun mit den Hilfsfunktionen realisiert.
<code id="4fb295a0080e1">
(define some-alphabet (list #\a #\b #\c #\d #\e))

(define exponents-product
  (lambda (prime-bases word-indexes)
    (if (and (null? prime-bases) (null? word-indexes))
      1
      (* (expt (car prime-bases) (car word-indexes)) (exponents-product (cdr prime-bases) (cdr word-indexes))))))

(define goedel
  (lambda (word)
    (let ((word-as-list (string->list word)))
      (exponents-product (fill-with-primes 1 (length word-as-list) '()) (fill-with-indexes word-as-list '() some-alphabet))))) 
</code>
Der Aufruf der Gödel-Funktion mit dem Wort aac liefert das Ergebnis 750. Diese Zahl ist die Gödelnummer dieses Wortes.
<run id="4fb295a008167">
(goedel "aac")
</run>

= Umkehrung der Gödelisierung =
Für die "Ent-Gödelisierung" muss nun aus einer Gödelnummer ein Wort aus der Wortmenge (Das Urbild der Abbildung) erzeugt werden, das mit der Gödel-Funktion benutzt wieder genau dieselbe Gödelnummer ergibt.