BuK/IIm10/BuK-Kreativaufgabe11 G1

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
<language>Scheme</language>
= Gödelisierung und µ-rekursive Funktionen =
== Aufgabe ==
Sei <math>h: S^{*} \rightarrow N_{0}</math> eine Gödelisierung von <math>S^{*}</math>, d.h. <math>h</math> ist injektiv, total und berechenbar. <math>h(S*)</math> ist entscheidbar und <math>h^{-1} : h(S^{*}) \rightarrow S^{*}</math> ist berechenbar.

Dann können die Wörter aus <math>S^{*}</math> vermöge <math>h</math> gödelgeordnet werden, so dass <math>w_{i} \prec w_{j} \Leftrightarrow h(w_{i}) < h(w_{j})</math>, für alle <math>w_{i},w_{j} \in S^{*}</math> und <math>w_{i} \neq w_{j}</math>.

Die folgende µ-rekursive Funktion liefert die Folge der Gödelnummern <math>h(w_{0}), h(w_{1}), . . . </math> in aufsteigender Form.

<math>g(1) = \mu f(n, i) = \begin{cases}
  \text{das kleinste } n \in N_{0}, \text{ mit } 1- p(0, n) = 0 & , \text{wenn}\\
  & \text{(1) so ein n existiert und}\\
  & \text{(2) }1-p(0,m) \text{ f\"ur alle } m <= n \text{ definiert ist} \\

  \text{undefiniert} & , \text{sonst}
\end{cases}</math>

Für <math>i \geq 1</math> gilt:

<math>g(i + 1) = \mu f(n, i) = \begin{cases}
  \text{das kleinste }n \in N_{0} \text{, mit }1 - p(g(i) + 1, n) = 0 &\text{, wenn} \\
   & \text{(1) so ein }n\text{ existiert und}\\
   & \text{(2) }1 - p(g(i) + 1,m)\text{ f\"ur alle }m \leq n\text{ definiert ist}\\
  \text{undefiniert} &\text{, sonst}\\
\end{cases}</math>

Die zur Definition von <math>g</math> verwendete zahlentheoretische Funktion <math>p</math> ist

<math>p(r, y) =\begin{cases}
  1 & \text{, wenn }y \geq r\text{ und }y\text{ ist G\"odelnummer}\\
  0 & \text{, sonst}
\end{cases}</math>

Illustrieren Sie die folgenden Aussagen durch den Einsatz selbst entwickelter Scheme-
Prozeduren. Wählen Sie exemplarisch <math> S = {a, b}</math> und die Verschlüsselung im 3er-System,
mit <math>a \rightarrow 1,  b \rightarrow 2</math> als Gödelisierung h mit <math>h(w) =
\Sigma ^{\|w\|-1}_{i=0} a_{i}*3^{i}</math> mit <math>a_{i} \in \{1,2\}</math>. Das Wort
aba erhält dann die Gödelnummer <math>h(aba) = 1*3^{2}+2*3^{1}+1*3^{0} = 16</math>. Nicht jede natürliche
Zahl ist Gödelnummer eines Wortes aus <math>S^{*}</math>: Beispielsweise ist <math>10 = 1 * 3^{2} + 0 * 3^{1} + 1 * 3^{0}</math>
keine.

<math> p: N_{0} \times N_{0} \rightarrow \{0,1\}</math> ist ein total berechenbares Prädikat. (Hinweis: Hierzu benötigen Sie eine Scheme-Prozedur für ein total berechenbares Prädikat, das feststellt, ob eine gegebene Zahl y Gödelnummer ist, d.h. y muss in der Form <math> \Sigma ^{n}_{i=0} a^{i}*3^{i}</math> mit <math>a_{i} \in \{1,2\}</math> darstellbar sein.)

<math>g: N \rightarrow N_{0}</math> wächst streng monoton und ist total. (Hinweis: Verwenden Sie eine Scheme-Prozedur zur Berechnung der ersten 10 Gödelnummern.)

Mit Hilfe der Funktion <math>k : N \rightarrow S^{*}, k(n) = h^{-1}(g(n))</math> kann man das <math>n</math>-te Wort in der gödelgeordneten Folge der Wörter aus <math>S^{*}</math> bestimmen. <math>k</math> ist total und injektiv. Die zugehörige Umkehrfunktion <math>k^{-1} : S^{*}  \rightarrow N</math> liefert somit auch wieder die Gödelisierung mit <math>k^{-1}(w_{n}) = h(n)</math>.



== Lösung ==
Die Lösung für die Funktion <math>h</math> lautet:
<code>
(define h (lambda (s)
  (letrec
    ((h-rekursiv (lambda (lst i gdlnummer)
      (cond
        ((equal? lst '()) gdlnummer)
         ((equal? (car lst) #\a) (h-rekursiv (cdr lst) (+ i 1) (+ gdlnummer (* 1 (expt 3 i)))))
         ((equal? (car lst) #\b) (h-rekursiv (cdr lst) (+ i 1) (+ gdlnummer (* 2 (expt 3 i)))))))))
      
  (h-rekursiv (string->list s) 0 0))))</code>
<run>(h "abbababba")</run>

Die Umkehrung der Funktion <math>h</math>, also <math>h^{-1}</math>, lautet:
<code>
(define hinvers (lambda (i)
  (letrec
    ((hinvershelp (lambda (i lst)
      (let ((num (floor (/ i 3))) (mod (modulo i 3)))
        (cond 
          ((and (= 0 num) (= 0 mod)) lst)
           ((= 1 mod) (hinvershelp num (cons #\a lst)))
           ((= 2 mod) (hinvershelp num (cons #\b lst))))))))
  (list->string (reverse (hinvershelp i '()))))))
</code>
<run>(hinvers 12850)</run>

Um heruaszufinden ob eine Zahl eine gültige Gödelnummer zu dem gegebenen System ist, kann die Funktion <math>h?</math> verwendet werden:
<code>
(define h? (lambda (n)
  (cond
    ((< n 3) #t)
     ((= 0 (modulo n 3)) #f)
     (else (h? (floor (/ n 3)))))))
</code>
<run>
(h? 12850)
</run>
<run>
(h? 14304)
</run>

Lösung für Funktion <math>g</math>
<code>
(define g (lambda (n)
  (letrec
    ((g-rekursiv (lambda (s i) 
       (if (p s i) i (g-rekursiv s (+ 1 i))))))
     (if (= n 1) (g-rekursiv 0 1) 
         (let ((n_p (+ 1 (g (- n 1))))) (g-rekursiv n_p n_p))))))
</code>
<run>

</run>

die zahlentheoretische Funktion <math>p</math>, ist nur eine Erweiterung von h? mit der zusätzlichen Bedingung, dass y größer gleich r sein muss:
<code>
(define p (lambda (r y)
  (cond
    ((and (>= y r) (h? y)) #t)
    (else #f))))
</code>
<run>
(p 8 14)
</run>
<run>
(p 7 9)
</run>

Funktion <math>k</math> muss nicht extra implementiert werden, da diese aus <math>h^{-1}</math>(also hinvers) und <math>g(n)</math> besteht:
<run>
(hinvers (g 7))
</run>

In Scheme sieht die Funktion <math>k^{-1}</math> so aus:
<code>
(define kinvers
  (lambda (wort)
    (letrec 
      ((kinvershelp (lambda (temp gVonN i)
         (cond
            ((= temp i) gVonN)
             ((h? i) (kinvershelp temp (+ 1 gVonN) (+ 1 i)))
             (else (kinvershelp temp gVonN (+ 1 i)))))))
      (kinvershelp (h wort) 0 0))))
</code>
<run>
(kinvers "abbababba")
</run>