Kleenesche Normalform
aus Wikipedia, der freien Enzyklopädie
Die kleensche Normalenform ist ein Begriff aus der Berechenbarkeitstheorie. Sie besagt, dass man jede partiell-rekursive Funktion mit Hilfe nur eines einzigen μ-Operators (While-Schleife) darstellen kann.
[Bearbeiten] Beweisidee
Um zu beweisen, dass jedes partiell-rekursive Funktion lediglich mit nur einer einzigen While-Schleife geschrieben werden kann, konstruieren wir uns ein universelles Programm, welches uns ein beliebiges Programm P ausführen kann. Dieses universelle Programm verarbeitet jeden Befehl aus P mit Hilfe von primitiv rekursiven Funktionen. Das universelle Programm terminiert genau dann, wenn die letzte Zeile des gegebenen Programms (o.B.d.A eine NOP-Anweisung) erreicht ist. Somit existiert in dem universellen Programm nur eine einzige While-Schleife, die genau dann terminiert, wenn der Programmzeilenzähler gleich der Länge des Programms ist.
Dieser Beweis zeigt auch, dass jede RAM-berechenbare Funktion in der Menge der partiell-rekursiven Funktionen ist.
