BuK/IIm18/Vorlesung7

Wiki-Quelltext dieser Seite.

== Eigenschaften der Gödelisierung ==

z.z.: Aus (1), (2) und (3) folgt (4)

(1): Jedem Element aus natürlichen Zahlen wird höchstens ein Element aus A* zugeordnet

(2) G(A*) ist berechenbar -> Es lässt sich eine Prozedur angeben, die G(w) in endlich vielen Schritten berechnet

(3) G(A*) ist entscheidbar -> Es lässt sich für jedes n von N in endlich vielen Schritten feststellen, ob n eine Gödelnummer ist

(4) es existiert eine berechenbare Umkehrfunktion zu allen Elementen in G(A*), um von G(A*) zu A* zu kommen

'''Herleitung von (4)'''

* Menge der natürlichen Zahlen ist aufzählbar -> 0,1,2,3….
** diese lasse ich mir generieren
* zu jedem n kann durch (3) festgestellt werden, ob n Gödelnummer ist
** Wenn ja, muss nun das Wort aus A* für das jeweilige n bestimmt werden
* A* ist ebenfalls aufzählbar -> längenlexigografische Ordnung aller Wörter möglich
** Wir bauen uns eine Generatorfunktion g für alle Wörter aus A*
** Lassen uns potentiell alle Wörter generieren
** Berechnen für jedes Wort durch (2) die Gödelnummer
** Das wird so lange gemacht, bis berechnete Gödelnummer mit unserem n übereinstimmt
** Dann haben wir für dieses n das Wort aus A* gefunden (Lösung erreicht)
* Durch (1) wird sichergestellt, dass für dieses n genau ein Wort aus A* existiert

<language>Java</language>
== Java-Programm zur Gödelisierung sowie zur Umkehrung mittels Primfaktorzerlegung ==
<code id="5cd88234a4415">
public class Application {

    public static void main(String[] args) {

        Alphabet alphabet = new Alphabet('a','b','c');
        GoedelisierungPrim goedelisierungPrim = new GoedelisierungPrim(alphabet);
        AStern aStern = new AStern(alphabet);
        aStern.stream()
                .limit(100)
                .peek(s -> System.out.print(s + " "))
                .map(goedelisierungPrim::getGoedelNumberFromWord)
                .peek(i -> System.out.print(i + " "))
                .map(goedelisierungPrim::getWordFromGoedelNumber)
                .forEach(System.out::println);
    }
}
</code>