BuK/IIm11/BuK-Übung07
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Scheme</language>
== 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) ==
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.
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 (sofern sie ebenso durch ein Programm lösbar sind).
=== Hilfsprozeduren ===
==== Stream-Prozeduren ====
<code id="4fb2ad291c4b8">
(define stream-car car)
(define stream-cdr
(lambda (stm)
(force (cdr stm))))
(define-syntax stream-cons
(syntax-rules ()
((_ head tail) (cons head (delay tail)))))
(define stream?
(lambda (stm)
(and (pair? stm)(promise? (cdr stm)))))
(define stream-item
(lambda (str nr)
(if(<= nr 0)
(stream-car str)
(stream-item (stream-cdr str) (- nr 1)))))
(define print-stream
(lambda (stm n)
(cond
((<= n 0) (display "...\n"))
(else
(display (stream-car stm))
(display ", ")
(print-stream (stream-cdr stm) (- n 1))))))
</code>
==== Prozeduren für Wortmengen-Stream ====
<code id="4fb2ad291c56a">
(define pow
(lambda (number exp)
(if (= exp 0)
1
(* number (pow number (- exp 1))))))
(define getElement
(lambda (set index)
(if (= index 1)
(car set)
(getElement (cdr set) (- index 1)))))
(define cardinalNumber
(lambda (set)
(if (null? set)
0
(+ 1 (cardinalNumber (cdr set))))))
(define calculateWordSize
(lambda (set index)
(letrec ((calculateWordSizeReal
(lambda (cardinalNumber index sum exp)
(if (>= sum index)
0
(+ 1
(calculateWordSizeReal
cardinalNumber
index
(+ sum (pow cardinalNumber exp))
(+ 1 exp)))))))
(calculateWordSizeReal (cardinalNumber set) index 0 1))))
;Berechnet die Anzahl der Wörter mit Länge <= letterCount
(define numberOfWords
(lambda (cardinalNumber letterCount)
(if (= letterCount 0)
0
(+
(pow cardinalNumber letterCount)
(numberOfWords cardinalNumber (- letterCount 1))))))
(define createWord
(lambda (set wordnumber cardinalNumber lettersRemaining)
(if (= 0 lettersRemaining)
""
(let ((sectionSize (pow cardinalNumber (- lettersRemaining 1))))
(let ((rest (modulo wordnumber sectionSize))
(result (quotient wordnumber sectionSize)))
(if (= 0 rest)
(string-append
(string (getElement set result))
(createWord set sectionSize cardinalNumber (- lettersRemaining 1)))
(string-append
(string (getElement set (+ result 1)))
(createWord set rest cardinalNumber (- lettersRemaining 1)))))))))
(define f
(lambda (testSet index)
(if (= index 0)
""
(let((cardinalNumber (cardinalNumber testSet))
(lettersRemaining (calculateWordSize testSet index)))
(createWord testSet (- index (numberOfWords cardinalNumber (- lettersRemaining 1))) cardinalNumber lettersRemaining)))))
</code>
==== Prozeduren für Primzahlenverschlüsselung ====
<code id="4fb2ad291c5f0">;; from presention nr. 3
(define prim?
(lambda (n)
(letrec
((helfer
(lambda (t)
(cond
((> t (sqrt n)) #t)
((= (remainder n t) 0) #f)
(else
(helfer (+ t 2)))))))
(cond
((= n 1) #f)
((= n 2) #t)
((= (remainder n 2) 0) #f)
(else
(helfer 3))))))
;; returns the next prime number that is larger than number
(define nextPrime
(lambda (number)
(let ((nextNumber (+ number 1)))
(if (prim? nextNumber)
nextNumber
(nextPrime nextNumber)))))
(define letterToindexGenerator
(lambda (list)
(lambda (letter)
(letrec ((worker (lambda (list letterNumber)
(if (equal? (car list) letter)
letterNumber
(worker (cdr list) (+ 1 letterNumber))))))
(worker list 1)))))
(define GGenerator
(lambda (letterFkt)
(lambda (word)
(letrec ((worker (lambda (word lastPrime)
(if (null? word)
1
(let (
(primeNr (nextPrime lastPrime))
(letterIndex (letterFkt (car word))))
(* (expt primeNr letterIndex) (worker (cdr word) primeNr)))))))
(worker (string->list word) 0)))))
</code>
== Hauptprozedur ==
Die Hauptprozedur für die Gödel-Funktion ist nun mit den Hilfsfunktionen realisiert.
<code id="4fb2ad291c66c">
(define some-alphabet (list #\a #\b #\c #\d))
(define letterToindexOfSomeAlphabet (letterToindexGenerator some-alphabet))
(define G (GGenerator letterToindexOfSomeAlphabet))
; Erzeuge Stream von A*
(define a-stream-maker
(lambda (index)
(stream-cons (f some-alphabet index) (a-stream-maker (+ index 1)))))
(define a-stream (a-stream-maker 1))
(define some-word (stream-item a-stream 333))
</code>
<run id="4fb2ad291c86d">
(display some-word)
(display "\n")
(G some-word)
</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.
=== Hilfsprozeduren ===
<code id="4fb2ad291c707">(define indexToLetterGenerator
(lambda (list)
(lambda (number)
(letrec ((worker (lambda (list letterNumber)
(if (= number letterNumber)
(car list)
(worker (cdr list) (+ 1 letterNumber))))))
(worker list 1)))))
(define getExponents
(lambda (number base)
(letrec ((worker (lambda (number)
(if (< number base)
(list number)
(let ((digit (if
(= (modulo number base) 0)
base
(modulo number base))))
(cons digit (worker (quotient number base))))))))
(worker number))))
(define numberToWord
(lambda (indexFkt number base) 0
(letrec ((worker (lambda (letterNumberList)
(if (null? letterNumberList)
'()
(cons (indexFkt (car letterNumberList)) (worker (cdr letterNumberList)))))))
(list->string (worker (getExponents number base))))))
(define primeProduktForBase
(lambda (number base)
(letrec ((worker (lambda (exponentList currentPrime)
(if (null? exponentList)
1
(let ((calculatedNextPrime (nextPrime currentPrime)))
(* (expt calculatedNextPrime (car exponentList)) (worker (cdr exponentList) calculatedNextPrime)))))))
(worker (getExponents number base) 1))))
(define GInvertedGenerator
(lambda (indexFkt letterCount)
(lambda (number)
(letrec ((worker (lambda (index)
(if (= (primeProduktForBase index letterCount) number)
(numberToWord indexFkt index letterCount)
(worker (+ 1 index))))))
(worker 0)))))
</code>
== Hauptprozedur ==
<code>
(define indexToLetterOfSomeAlphabet (indexToLetterGenerator some-alphabet))
(define GInverted (GInvertedGenerator indexToLetterOfSomeAlphabet (length some-alphabet)))
</code>
<run id="4fb2ad291cca2">(GInverted 7938000)</run>
== 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)))$