Die Kleenesche Normalform ist ein Begriff aus der Berechenbarkeitstheorie. Sie besagt, dass man jede partiell-rekursive Funktion mit Hilfe nur eines einzigen μ-Operators (While-Schleife) darstellen kann.
Beweisidee Bearbeiten
Um zu beweisen, dass jede partiell-rekursive Funktion 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.