Kleenesche normal form
The Kleene normal form is a term used in computability theory . It says that every partially recursive function can be represented with the help of just a single μ-operator ( while loop ).
Proof idea
In order to prove that every partially recursive function can be written with just a single while loop, we construct a universal program that any program P can execute. This universal program processes every instruction from P with the help of primitive recursive functions . The universal program terminates exactly when the last line of the given program (or e.g. a NOP statement) is reached. This means that there is only one while loop in the universal program, which terminates precisely when the program line counter is equal to the length of the program.
This proof also shows that every RAM -computable function is in the set of partially recursive functions .