BuK/IIm11/BuK-Übung07

Wiki-Quelltext dieser Seite.

== Eigenschaften der Gödelisierung (Stefan Scheumann, Ronald Krause, Tobias Salzmann, Robert Rosenberger) ==

Eine Abbildung $G : A^* \rightarrow \N$ heißt <b>Gödelisierung von </b>$A^*$, wenn die folgenden Bedingungen erfüllt sind:

(1) $G$ ist injektiv, d.h. für alle $w, w'\in A^*$ gilt: Wenn $w \neq w'$, dann $G(w) \neq G(w^')$

(2) $G$ ist berechenbar, d.h. zu jedem Wort $w \in A^*$ lässt sich $G(w)$ in endlich vielen Schritten berechnen.

(3) $G(A^*)$ ist entscheidbar, d.h. für jedes n \in \N lässt sich in endlich vielen Schritten feststellen, ob $n \in G(A^*)$ gilt oder nicht.

(4) Die Umkehrfunktion $G^{-1} : G(A^*) \rightarrow A^*$ ist berechenbar, d.h. zu jedem $n \in G(A^*)$ lässt sich das Wort $w$ mit $G(w) = n$ in endlich vielen Schritten auffinden. (<b>Übungsaufgabe: </b>(4) folgt aus (1)-(3).)


'''Zu Zeigen:''' $G^{-1} : G(A^*) \rightarrow A^*$ ist berechenbar.


Hierfür werden die ersten drei Eigenschaften der Gödelisierung benötigt:

Da $G$ injektiv ist, lässt sich eine Aufzählprozedur angeben, welche jedes Wort aus A* aufzählt, dass heißt Wörter welche zu $G(A^*)$ gehören oder nicht.

Da $G$ berechenbar ist, kann eine Prozedur angegeben werden, welche die entsprechende Gödelnummer liefert.

Da $G(A^*)$ auch entscheidbar ist, lässt sich genau bestimmen, ob ein Wort aus $A^*$ zu $G(A^*)$ gehört oder nicht.


Da $G(A^*)$ berechenbar ist, kann durch das Ausführen von $G(A^*)$, die zurückgebene Gödelunumer, mit der von $G^{-1}$ verglichen werden.

Da $G(A^*)$ ebenfalls entscheidbar ist und jedes Wort aus $A^*$ durch $G(A^*)$ aufgezählt wird, kann durch die Umkehrfunktion genau entschieden werden, ob ein Wort aus $A^*$ für die Gödelnummer existiert oder nicht.

== Primzahlverschlüsselung (Ingo Körner, Christof Ochmann, Raik Bieniek, Max Wielsch) ==
<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.

== Prinzip der Gödelisierung (Daniel Tasche, Jens Heider, Felix Nitsche, Stefan Lüttke) ==

$f : G(A^*) \rightarrow G(A^*) und h : A^* \rightarrow A^*$ sind Funktionen. $f$ ist eine berechenbare Funktion genau dann, wenn $h$ eine berechenbare Funktion ist.

<b>Beweis</b> als Übungsaufgabe: argumentativ für $h = G^{-1}  \circ f \circ G$ und $f = G \circ h \circ G^{-1}$ unter Bezugnahme auf das Prinzip der Gödelisierung.

-----

[[File:Goedelisierung_01_sifenits.png|Darstellung]]

Da G und G^{-1} berechenbar sind, lassen sich $f(x)$ oder $h(x)$ mit den jeweils verbleibenden Funktionen ausdrücken.

- wenn $f$ berechenbar ist:

$h(x) = G(f(G^{-1}(x)))$

- wenn $h$ berechenbar ist:

$f(x) = G^{-1}(h(G(x)))$