Primitive recursive function: Difference between revisions

Revision as of 05:11, 1 March 2002

Revision as of 05:29, 1 March 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 [[operator|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 "[[computation|computable]]"; see [[Equivalence of models of computation]]).