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).)
[[File:Gödelisierung.png|center|Grafische Darstellung]]
'''z.z.''' ist, dass Bedingung 4 aus den ersten drei Eigenschaften folgt.
$G$ ist die Funktion für $A^* \rightarrow \N$.
$G(A^*)$ ist die Menge von Gödelnummern.
(1) Jedes Wort aus der Definitionsmenge $A^*$ hat einen Funktionswert $G(w)$.
(2) Es gibt eine Prozedur, welche zu jedem Wort aus $A^*$ (genau eine) Gödelnummer zurückgibt.
(3) Es gibt eine Prozedur, welche entscheidet, ob eine natürliche Zahl eine Gödelnummer ist oder nicht.
----
Laut Bedingung 4 gibt es eine Umkehrfunktion, welche ein Wort aus $A^*$ für eine Gödelnummer zurückgibt. Das heißt, dass zu jeder natürlichen Zahl, welche zur Menge $G(A^*)$ gehört, sich das Wort $w$ mit $G(w)=n$ in endlich vielen Schritten zurückgibt.
Aus Bedingung (3) ergibt sich, dass für jede natürliche Zahl entschieden werden kann, ob es eine Gödelnummer ist oder nicht.
Aus Bedingung (2) kann zu jeden Wort $w$ aus $A^*$ eine Gödelnummer bestimmt werden.
Aus (3) und (2) folgt, dass beide Gödelnummern miteinander verglichen werden können, wodurch bei einer Gleichheit der Gödelnummern, dass Wort $w$ aus $A^*$ zurückgegeben werden kann.
Aus der Injektivität lt. (1) ergibt sich, dass es für ein Wort $w$ aus $A^*$ eine Gödelnummer gibt, sodass das Wort nach einer Übereinstimmung der Gödelnummern eindeutig ist.
Durch die Aufzählfunktion für $A^*$ werden alle möglichen Wörter aus der Wortmenge betrachtet.
== 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 id="4fc4991dc4812">
(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)))$