ue7

Aus ProgrammingWiki

Inhaltsverzeichnis

1 Gödelisierung
- 1.1 Hilfsprozeduren
- 1.2 Hauptprozedur
2 Umkehrung der Gödelisierung

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.

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

Hauptprozedur

Die Hauptprozedur für die Gödel-Funktion ist nun mit den Hilfsfunktionen realisiert.

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

Der Aufruf der Gödel-Funktion mit dem Wort aac liefert das Ergebnis 750. Diese Zahl ist die Gödelnummer dieses Wortes.

(goedel "aac")

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.

ue7

Inhaltsverzeichnis

Gödelisierung

Hilfsprozeduren

Hauptprozedur

Umkehrung der Gödelisierung

Suche