Primitive recursive function: Difference between revisions

Revision as of 16:33, 7 December 2001

Revision as of 17:24, 7 December 2001

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]] asand the[[composition]] as central operationoperations. The primitive recursive functions are a [[subset]] of the [[computable functions|recursive functions]] (which are exactly those functions

functions (which are exactly those functions

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

Line 11 ⟶ 9:

Primitive recursive functions are functions which take one or several [[natural numbers]] as arguments and produce a natural number as value. A function which takes ''n'' arguments will beis called ''n''-[[arity|ary]]. They are defined as follows.:

The initial set of [[axiom|axioms]]:

Start with the following functions:

Line 21 ⟶ 19:

#The [[constant term|constant]] function 0 is primitive recursive.

#The "successor function" ''S'', definedwhich bytakes ''S''(''k'')one =argument ''k''and +returns 1the succeeding number on the natural [[number line]], is primitive recursive.

#The "projection functions" ''P''_''i''^''n'', awhich function oftake ''n'' arguments whichand returnsreturn itstheir ''i''th argument, are primitive recursive.

The set of [[operators]]:

Now consider the following operations:

Line 33 ⟶ 31:

#''Composition'': Given ''f'' a ''k''-ary primitive recursive function and ''k'' ''l''-ary primitive recursive functions ''g''₀,...,''g''_''k''-1, the [[composition]] of ''f'' with ''g''₀,...,''g''_''k''-1, i.e. the function ''h''(''x''₀,...,''x''_''l''-1) = ''f''(''g''₀(''x''₀,...,''x''_''l''-1),...,''g''_''k''-1(''x''₀,...,''x''_''l''-1)), is primitive recursive.

#''Primitive recursion'': Given ''f'' a ''k''-ary primitive recursive function and ''g'' a (''k''+2)-ary primitive recursive function, then the (''k''+1)-ary function defined as the primitive recursion of ''f'' and ''g'', i.e. the function ''h'' where ''h''(0,''x''₀,...,''x''_''k''-1) = ''f''(''x''₀,...,''x''_''k''-1) and ''h''(''n''+1,''x''₀,...,''x''_''k''-1) = ''g''(''n'',''h''(''n'',''x''₀,...,''x''_''k''-1),''x''₀,...,''x''_''k''-1)), is primitive recursive.

AllThe set of primitive recursive functions are the closure of the initial set of terms over these operators, i.e. the set of all functions that can be generated by repeated application of these rules to the basic functions defined above form the set of primitive recursive functions.

Line 65 ⟶ 63:

Primitive recursive functions tend to correspond very closely with our intuition of what a computable function must be. Certainly the initial set of functions are intuitively computable (in their very simplicity), and the two operations by which one can create new primitive recursive functions are also very straight-forwardstraightforward. However the set of primitive recursive functions does not include every possible computable function -- this can be seen with a variant of [[Cantors Diagonal argument|Cantor's diagonalization argument]].

(''need outline of proof'')

----

[[/Talk]]