BuK/IIm10/BuK-Kreativaufgabe11 G2

Wiki-Quelltext dieser Seite.

<language>Java</language>
= Gödelisierung =

== Aufgabe ==
Gegeben ist ein Alphabet <math>{S}^{*}</math>, mit <math>S={a,b}</math> in der Verschlüsselung im 3er-System, mit 
<math>a\rightarrow 1</math> und <math>b\rightarrow 2</math>. Die Gödelisierungsfunktion <math>h</math> von <math>
{S}^{*}</math> ist so definiert:

<math>h(w) = \sum^{|w|-1}_{i=0}{a}_{i}*{3}^{i}</math> mit <math>{a}_{i} \in \{1,2\}</math>

Die Funktion <math>p: N \times N \mapsto \{0,1\}</math> ist ein total berechenbares Prädikat. Sie stelt für eine 
beliebige natürliche Zahl <math>n</math> fest, ob diese eine Gödelnummer (des oben genannten Algorithmus) ist oder 
nicht.

Eine Funktion <math>g: \N \mapsto \N</math> wächst streng monoton und ist total. Sie listet alle Gödelnummern für 
diesen Algorithmus auf.

Die Funktion <math>k: N \mapsto {}^{*}, k(n)={h}^{-1}(g(n))</math> ist die Umkehrfunktion von h und nimmt eine 
Gödelnummer und liefert ein Wort aus <math>{S}^{*}</math>

Diese Funktionen sollen als Prozeduren in Scheme illustriert werden.

== Lösung ==
<code id="4dff90fc83ead" hidden>

(define mystringreverse
  (lambda (str)
    (list->string (myreverse (string->list str)))
  )) 
        
(define myreverse
  (lambda (ls)
    (if (null? ls)
        ls
        (append
         (myreverse (cdr ls))
         (list (car ls))))))

(module wortmenge Racket
  (provide wortmenge-stufe wortmenge-bis-stufe)

(define wortmenge-stufe
  (lambda (n alphabet)
    (if (= n 0)
        '("")
        (apply
         append
         (map 
          (lambda (zeichen)
            (map
             (lambda (wort)(string-append  (string zeichen)wort))
             (wortmenge-stufe (- n 1) alphabet)))
          alphabet)))))

(define wortmenge-bis-stufe
  (lambda (n alphabet)
    (if (= n 0)
        (wortmenge-stufe 0 alphabet)
         (append 
          (wortmenge-bis-stufe (- n 1) alphabet)
          (wortmenge-stufe n alphabet)))))
        
  





(define S '("a" "b")) ;Alphabet
(define Scode '(1 2)) ;Alphabet-Kodierung
;help procedures for h
(define h_helper
  (lambda (w i)
     (list-ref Scode (get-i-te-Element_index (get-i-te-Element_content w i)))
  ))

(define get-i-te-Element_content
  (lambda (str i)
    (string (list-ref (string->list str) i))
    ))

(define get-i-te-Element_index
  (lambda (str)
    (get-indices str S)  
))


;get (OUT) i from (IN) element and list
(define get-indices 
  (lambda (letter liste)
  (define (loop rest-of-liste index)
    (if (null? rest-of-liste) 'exeption
      (let ((rest-of-indices (loop (cdr rest-of-liste) (+ index 1))))
        (if (equal? (car rest-of-liste) letter)
          index
          rest-of-indices))))
  (loop liste 0)))


</code>

Die Funktion <math>h</math> rechent für ein gegebenes Wort den mathematischen Ausdruck aus.
<code id="4dff8f938bf3c">
(define h
  (lambda (w)
    (define sum 0)
    ;SUM{i=0}{|w|-1}{ai * 3^i}
      (do ((i 0 (+ i 1))) ((> i (- (length (string->list w)) 1)))
        (set! sum (+ sum (* (h_helper w i) (expt (+ 1 (length S)) i))))
        )
    sum
))
</code>

<run id="4dff8f938c20a">
(h 16)
</run>

Das Prädikat <math>p</math> prüft ob quasi ob die gegebene Zahl mit dieser Bildsungsvorschrift erzeugt werden kann 
oder nicht.

<code id="4dff8f938bfe0">
(define p
  (lambda (y)
    (if (gödelnr? y)
     1
     0)
 ))

(define gödelnr?
 (lambda (y)
    (if (= 0 y)
        #t
        (if (= 0 (modulo y (+ 1 (length S))))
            #f
            (gödelnr? (floor (/ y (+ 1 (length S))))))
        )
   ))
</code>
Die Zahl <math>16</math> ist im Gegensatz zur <math>15</math> eine Gödelnummer. Beide Aufrufe liefert 

<math>WAHR</math>, da diese mit dem Erwarteten Wert getestet werden.
<run id="4dff8f938c297">
(equal? (gödelnr? 16) #t)
(equal? (gödelnr? 15) #f)
</run>

Mit dieser Prädikatsfunktion ist es ein leichtes die Funktion für die Auflistung zu schreiben. Man geht alle 
natürlichen Zahlen bis zu einem Maximum durch und immer wenn diese Zahl eine Gödelnummer ist, dann wird sie zu 
einer Liste hinzufgefügt. 
<code id="4dff8f938c073">
(define g
  (lambda (max)
    (g_helper 1 max '())
))

(define g_helper
  (lambda (i max liste)
    (if (< (length liste) max)
        (and   
         (if (gödelnr? i) 
            (g_helper (+ i 1) max (append liste (list i)))
            (g_helper (+ i 1) max liste)))
        liste)
))
</code>
<run id="4dff8f938c31f">
(g 100)
</run>

Für Funktion <math>k</math> wird die Berechenbarkeit der Funktion <math>g</math> und die Aufzählbarkeit des 

Alphabets <math>{S}^{*}</math> ausgenutzt. Genau diese beiden Mengen werden aufgezählt und sind gleichmächtig. 

Der Algorithmus <math>k</math> arbeitet so:
# Auflistung aller Gödelnummern (Funktion g)
# Der Indizes der passenden Gödelnummer wird gesucht und immer gefunden, falls Gödelnummer existiert
# Eine Liste, in der <math>{S}^{*}</math> aufgezählt wird, wird erzeugt.
# Aus dieser Liste, wird anhandes des gefundenen Indezes das Wort herausgenommen.
# Da <math>k</math> "rückwärts" arbeitet, muss noch das Reverse genommen werden.

<code id="4dff8f938c137">
(define k
  (lambda (n)
    (mystringreverse (list-ref (f) (+ (get-indices n (g n)) 0)))
))
(define f
  (lambda ()
  (cdr (wortmenge-bis-stufe 7 (string->list "ab")));5 = Stufe 
))
</code>

Folgende verschachtelteAufrufe sollen die Eigenschaft dass <math>k(n)={h}^{-1}(g(n))</math> ist, durch Tests 
demonstrieren.

<run id="4dff8f938c3ae">
 (= (h (k (h "aba"))) (h (k 16)))
 (= (h (k (h "aabbba"))) (h (k 481)))
</run>