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.

Beweisidee

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.dA. 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.

Siehe auch

Trenner
Basierend auf einem Artikel in: Extern Wikipedia.de
Seitenende
Seite zurück
©  biancahoegel.de
Datum der letzten Änderung: Jena, den: 28.04. 2020