Kleenesche Normalform

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.

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.

• Partiell-rekursive Funktion
• Primitiv-rekursive Funktion
• While-Programm

• Berechenbarkeitstheorie
• Normalform