Direkt zum Inhalt

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 \begin{eqnarray}f({x}_{1},\,\ldots \,,\,{x}_{n})\,=\,U(\mu yT(k,\,{x}_{1},\,\ldots \,,\,{x}_{n},\,y))\end{eqnarray}für alle x1, …, xn.

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.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos