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


<language>Java</language>
== 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
* Die Funktion k ruft intern die μ-rekursive Funktion auf, um die i-te Gödelnummer zu berechnen. Mit der Umkehrfunktion der Gödelisierung wird daraus dann das Wort berechnet

<code id="5d06746adf42d">

</code>