Primitive recursive function  From Wikipedia, the free
encyclopedia   (Redirected from Primitive recursive functions)
Jump to: navigation, search  In computability theory, primitive
recursive functions are a class of functions that are defined
using primitive recursion and composition as central operations
and are a strict subset of the total µ-recursive functions
(µ-recursive functions are also called partial recursive).
Primitive recursive functions form an important building block
on the way to a full formalization of computability. These
functions are also important in proof theory. The term was
coined by Rózsa Péter.  Most of the functions normally studied
in number theory are primitive recursive. For example: addition,
division, factorial, exponential and the nth prime are all
primitive recursive. So are many approximations to real-valued
functions.[1] In fact, it is difficult to devise a computable
function that is not primitive recursive, although some are
known (see the section on Limitations below).