Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Primitive recursive function
Summary
In computability theory, a primitive recursive function is, roughly speaking, a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number of iterations of every loop can be determined before entering the loop). Primitive recursive functions form a strict subset of those general recursive functions that are also total functions.
The importance of primitive recursive functions lies in the fact that most computable functions that are studied in number theory (and more generally in mathematics) are primitive recursive. For example, addition and division, the factorial and exponential function, and the function which returns the nth prime are all primitive recursive. In fact, for showing that a computable function is primitive recursive, it suffices to show that its time complexity is bounded above by a primitive recursive function of the input size. It is hence not that easy to devise a computable function that is not primitive recursive; some examples are shown in section below.
The set of primitive recursive functions is known as PR in computational complexity theory.
A primitive recursive function takes a fixed number of arguments, each a natural number (nonnegative integer: {0, 1, 2, ...}), and returns a natural number. If it takes n arguments it is called n-ary.
The basic primitive recursive functions are given by these axioms:
More complex primitive recursive functions can be obtained by applying the operations given by these axioms:
The primitive recursive functions are the basic functions and those obtained from the basic functions by applying these operations a finite number of times.
A definition of the 2-ary function , to compute the sum of its arguments, can be obtained using the primitive recursion operator . To this end, the well-known equations
are "rephrased in primitive recursive function terminology": In the definition of , the first equation suggests to choose to obtain ; the second equation suggests to choose to obtain .
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.