Primitive Recursive Function

Primitive Recursive Function

The primitive recursive functions 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). The term was coined by Rózsa Péter.

In computability theory, primitive recursive functions are a class of functions that form an important building block on the way to a full formalization of computability. These functions are also important in proof theory.

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. 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). The set of primitive recursive functions is known as PR in complexity theory.

Every primitive recursive function is a general recursive function.

Read more about Primitive Recursive Function:  Definition, Examples, Relationship To Recursive Functions, Limitations, Some Common Primitive Recursive Functions, Additional Primitive Recursive Forms, Finitism and Consistency Results

Famous quotes containing the words primitive and/or function:

    “These modern ingenious sciences and arts do not affect me as those more venerable arts of hunting and fishing, and even of husbandry in its primitive and simple form; as ancient and honorable trades as the sun and moon and winds pursue, coeval with the faculties of man, and invented when these were invented. We do not know their John Gutenberg, or Richard Arkwright, though the poets would fain make them to have been gradually learned and taught.”
    —Henry David Thoreau (1817–1862)

    “Uses are always much broader than functions, and usually far less contentious. The word function carries overtones of purpose and propriety, of concern with why something was developed rather than with how it has actually been found useful. The function of automobiles is to transport people and objects, but they are used for a variety of other purposes—as homes, offices, bedrooms, henhouses, jetties, breakwaters, even offensive weapons.”
    —Frank Smith (b. 1928)