IIm18-Kreativaufgabe9

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
• 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