Primitive recursive function: Difference between revisions

Revision as of 14:07, 15 September 2003

Revision as of 02:06, 1 October 2003

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 [[Equivalenceequivalence of models of computation]]) and [[Church-Turing thesis]].

=== Definition ===