Primitive Recursive Functions, References?

I am fairly familiar with the primitive recursive functions, but there
is not much information on the topic I could find on the internet.
Could someone direct me towards relevant resources?

It is interesting to note that for quite some time the primitive
recursive functions were thought to exhaust -all- computable functions.
Ackermann's function, which uses double induction, shows this is not
the case, as does a simple diagonal argument using the fact that all
primitive recursive functions are total. However, any recursively
enumerable set is the image of some PR function, and one could argue in
the vein of the Church-Turing thesis that the PR functions form the
intuitive class of 'iteration functions,' i.e. the transition functions
from one state to the next in effective computation models.

Being a mathematics graduate student, what is the CS view of primitive
recursive functions and their role?

Rex Butler

.

Relevant Pages

  • Re: All panduks are green
    ... *If* you can represent all primitive recursive functions, ... and your theory is consistent, and your theory is r.e., ... But T cannot prove the statement "forall x, ...
    (sci.logic)
  • Re: All panduks are green
    ... *If* you can represent all primitive recursive functions, ... and your theory is consistent, and your theory is r.e., ... But T cannot prove the statement "forall x, ...
    (sci.logic)
  • Re: All panduks are green
    ... *If* you can represent all primitive recursive functions, ... and your theory is consistent, and your theory is r.e., ... But T cannot prove the statement "forall x, ...
    (sci.logic)
  • Re: Primitive Recursive Arithmetic - formulation?
    ... recursive functions for each arity. ... But we can enumerate the primitive ... there are no *explicit* quantifiers. ... have axioms for all the primitive recursive functions. ...
    (sci.logic)
  • Re: Primitive Recursive Arithmetic - formulation?
    ... recursive functions for each arity. ... But we can enumerate the primitive ... there are no *explicit* quantifiers. ... have axioms for all the primitive recursive functions. ...
    (sci.logic)
Quantcast