[Home]History of Primitive recursive function

HomePage | Recent Changes | Preferences
Revision 11 . . (edit) December 17, 2001 11:28 pm by Wmorgan [more small changes in the interest of clarity]
Revision 10 . . December 15, 2001 6:58 am by AxelBoldt [minor copyedit, link to Ackermann function]
Revision 9 . . December 15, 2001 1:40 am by Wmorgan [added example definitions and proof that p.r. functions are a subset of recursive ones; other minor changes.]
Revision 8 . . December 8, 2001 6:53 am by AxelBoldt
Revision 7 . . December 8, 2001 1:24 am by Wmorgan [fixups (see /Talk)]
Revision 6 . . December 8, 2001 12:33 am by AxelBoldt [copyedit]
Revision 5 . . December 8, 2001 12:32 am by AxelBoldt [copyedit]
Revision 4 . . December 8, 2001 12:29 am by AxelBoldt [copyedit]
Revision 3 . . December 8, 2001 12:28 am by AxelBoldt [copyedit]
Revision 2 . . December 8, 2001 12:26 am by AxelBoldt [copyedit]
Revision 1 . . December 8, 2001 12:10 am by (logged).153.190.xxx [new location]
  
Difference (from prior major revision) (minor diff, author diff)

Changed: 15c15
#Primitive recursion: Given f a k-ary primitive recursive function and g a (k+2)-ary primitive recursive function, the (k+1)-ary function defined as the primitive recursion of f and g, i.e. the function h where h(0,x0,...,xk-1) = f(x0,...,xk-1) and h(S(n),x0,...,xk-1) = g(h(n,x0,...,xk-1),n,x0,...,xk-1)), is primitive recursive.
#Primitive recursion: Given f a k-ary primitive recursive function and g a (k+2)-ary primitive recursive function, the (k+1)-ary function defined as the primitive recursion of f and g, i.e. the function h where h(0,x0,...,xk-1) = f(x0,...,xk-1) and h(S(n),x0,...,xk-1) = g(h(n,x0,...,xk-1),n,x0,...,xk-1), is primitive recursive.

Changed: 31c31
::add(n+1,x)=S(P03(add(n,x),n,x))
::add(S(n),x)=S(P03(add(n,x),n,x))

Changed: 33c33
:Note that P01 is simply the identity function; its inclusion is required by the definition of the primitive recursion operator above.
:Note that P01 is simply the identity function; its inclusion is required by the definition of the primitive recursion operator above; it plays the role of h. The composition of S and P03, which is primitive recursive, plays the role of g.

Changed: 39c39
::pred(0)=0
::pred(0)=0

Changed: 45c45
::pred(n+1)=P12(pred(n),n)
::pred(S(n))=P12(pred(n),n)

Changed: 52c52
:(note that the arguments have been switched from the "standard" definition to fit the requirements of primitive recursion, i.e. sub(a,b) corresponds to b-a.
:(Note that for the sake of simplicity, the order of the arguments has been switched from the "standard" definition to fit the requirements of primitive recursion, i.e. sub(a,b) corresponds to b-a. This could easily be rectified using composition with suitable projections.)

Changed: 54c54
Many other familiar functions can be shown to be primitive recursive; some examples include conditionals, exponentiation, [primality testing]?, and course-of-values induction.
Many other familiar functions can be shown to be primitive recursive; some examples include conditionals, exponentiation?, [primality testing]?, and course-of-values induction.

Changed: 56c56

Primitive recursive functions are a subset of the recursive functions



Primitive recursive functions are a proper subset of the recursive functions




Changed: 58c58
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 straightforward. However the set of primitive recursive functions does not include every possible computable function -- this can be seen with a variant of Cantor's diagonalization argument. This argument provides a computable function which is not primitive recursive. A sketch of the proof is as follows:
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 straightforward. However the set of primitive recursive functions does not include every possible computable function --- this can be seen with a variant of Cantor's diagonalization argument. This argument provides a computable function which is not primitive recursive. A sketch of the proof is as follows:

Changed: 60c60
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 operator). The numbering is computable in the sense that, given an index x and a value y, one can build a Turing machine to compute the xth primitive recursive function on input y (though an appeal to the Church-Turing thesis is likely sufficient to make the case).
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 operator). The numbering is computable in the sense that one can build a a Turing machine that, given an index x and a value y, computes the value of the xth primitive recursive function on input y (though an appeal to the Church-Turing thesis is likely sufficient to make the case).

Added: 66a67,68

One can also explicitly exhibit a simple 1-ary computable function which is recursively defined for any natural number, but which is not primitive recursive, see Ackermann function.
HomePage | Recent Changes | Preferences
Search: