Primitive recursive function

From Wiki @ Karl Jones dot com
Revision as of 06:45, 20 September 2016 by Karl Jones (Talk | contribs) (Created page with "In computability theory, '''primitive recursive functions''' are a class of functions that are defined using primitive recursion and Function...")

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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.

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 total recursive function that is not primitive recursive, although some are known.

The set of primitive recursive functions is known as PR in computational complexity theory.

See also

External links