Lexikon der Mathematik: Kleenesches Normalformtheorem
wichtiger Satz innerhalb der Berechnungstheorie, aufgestellt von von S.C. Kleene im Jahre 1936:
Für jedes n ∈ ℕ0gibt es eine einstellige primitiv-rekursive Funktion U und ein (n + 2)-stelliges primitiv-rekursives Prädikat T so, daß zu jeder n-stelligen μ-rekursiven Funktion f ein k ∈ ℕ0existiert mit
Inhaltlich besagt der Satz, daß man bei der Definition einer beliebigen µ-rekursiven Funktion mit höchstens einer Anwendung des µ-Operators auskommt.
Das Resultat läßt sich leicht auf imperative Programmiersprachen übertragen: So kommt im Prinzip jedes PASCAL- oder WHILE-Programm mit einer einzigen WHILE-Schleife aus.
Schreiben Sie uns!