BuK/IIm18/IIm18-Kreativaufgabe9

Wiki-Quelltext dieser Seite.

== Kernaussagen der Vorlesung ==

* nicht alle total berechenbare Funktionen sind primitv-rekursiv (AP-Funktion)
* man kann keine nicht totale Funktion als primitiv-rekursive Funktion darstellen
* man kann mit dem unbeschränkten μ-Operator μ-rekursive (d.h. partiell-rekursive) Funktionen darstellen. Diese sind so aufgebaut, dass es zu einem Endloszyklus kommen kann, wenn die geforderte Bedingung niemals erfüllt werden kann
* Die Menge der Turing-berechenbaren Funktionen und die Menge der μ-rekursiven Funktionen (partiell berechenbare Funktionen) sind identisch 
* μ-rekursive Funktionen können mit while-Programmen implementiert werden


== Implementierung der Kreativaufgabe (Java) ==

* Das folgende Programm implementiert die Funktion k. Mit dieser kann das Wort aus dem Alphabet S* für die n-te Gödelnummer (unterliegt Gödelordnung) berechnet werden