Primitive recursive function: Difference between revisions

Revision as of 15:36, 7 December 2001

Revision as of 15:49, 7 December 2001

Line 1:

Primitive recursive [[function|functions]] are a class of functions which, while a [[subset]] of the [[computable functions|recursive]]

functions (which themselves are exactly those functions

which we call "[[computationcomputatable functions|computable]]" -- see [[Equivalence of models of computation]]), are an important building block

on the way to a full formalization of computability.

Line 17:

:#The [[constant term|constant]] 0 is p.r.

:#The "successor function" ''S'' is p.r.

:#The "projection functions" ''P''_''i''^''n'' are p.r.

Line 27:

Where the "successor function" takes the number ''k'' and returns the number

one greater than ''k'' on the natural [[number line]], and the "projection

functions" ''P''_''i''^''n'' take n arguments and return the ''i''th one.

Line 37:

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

#''Primitive recursion'': Given ''f'' a ''k''-ary p.r. function and ''g'' a (''k''+2)-ary p.r. function, then the (''k''+1)-ary function defined as the primitive recursion of ''f'' and ''g'' is p.r., 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 p.r.

Line 55:

:#[[addition]]

:#[[subtraction]]

:#[[exponentiation]]

Line 71:

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 p.r. functions are also very straight-forward. However the set of p.r. 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/explanation'')

(''need outline of proof/explanation'')