Primitive recursive function: Difference between revisions

Revision as of 01:19, 2 January 2002

Revision as of 01:31, 2 January 2002

Line 1:

'''Primitive recursive functions''' are a class of functions which form an important building block on the way to a full formalization of computability. They are defined using [[recursion]] and [[composition]] as central operations. The primitive recursive functions are a strict [[subset]] of the [[recursive function|recursive functions]] (which are exactly those functions

which we call "[[computatable functioncomputation|computable]]" --; see [[Equivalence of models of computation]]).

Line 39:

=== Example primitive recursive function definitions ===

Line 105:

Many other familiar functions can be shown to be primitive recursive; some examples include [[conditional|conditionals]], [[exponentiation]], [[primality testing]], and [[Mathematical induction|course-of-values induction]], and the primitive recursive functions can be extended to operate on other objects such as integer and rational numbers.

=== Primitive recursive functions are a proper subsetLimitations of the primitive recursive functions ===

Line 117:

The primitive recursive functions can be computably numbered. This numbering is unique on the definitions of functions, though not unique on the actual functions themselves (as every function can have an infinite number of definitions --- consider simply composing by the [[identity function|identity operator]]). The numbering is computable in the sense that oneit can buildbe adefined aunder [[Turingformat machine]]models that,of givencomputability ansuch indexas ''x''[[Recursive andfunction|recursive afunctions]] valueor ''y'',[[Turing computesmachine|Turing the value of the ''x''th primitive recursive function on input ''y''machines]]; (thoughbut an appeal to the [[Church-Turing thesis]] is likely sufficient to make the case).

Line 141:

The set of primitive recursive functions does not encompass everything that we think of as computable. Nevertheless they form an important class and many of the functions normally studied in number theory, and approximations to real-valued functions, are primitive recursive.

By extending the definition of primitive recursive functions to allow for [[partial function|partial functions]] and by adding the concept of an unbounded search operator (see [[Recursive function]]), we arrive at a full formal model of computability -- the [[recursive function|recursive]] or [[recursive function|computable]] functions.

In order to formalize the full class of computable functions, we must introduce an additional operator to the above: the ''unbounded search'' operator (see [[Recursive function]]).