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 μ-Operator μ-rekursive (d.h. partiell-rekursive) Funktionen darstellen. Diese sind so aufgebaut, dass man weiß wie oft eine Funktion höchstens durchlaufen wird (obere Schranke) -> damit lassen sich nun auch * nicht totale Funktion sowie alle primitiv-rekursive Funktionen darstellen
* 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