will replacing the usual schema of primitive recursion: $$ f(0,\vec x) = c (\vec x)\\ f(n+1,\vec x) = g(f(n,\vec x), n, \vec x) $$ by the form: $$ f(0,\vec x) = c(\vec x)\\ f(n+1,\vec x) = g(f(n,\vec x)) $$

lead to the same class of primitive recursive functions?

  • $\begingroup$ If you can define products absolutely, otherwise maybe not.. $\endgroup$ Jan 11, 2016 at 12:32
  • $\begingroup$ This looks like an exercise in computability theory. If not please explain why are you interested in this question. Please also check our help center for description of the scope of this site and suggestions for other sites in case your question is off-topic here. $\endgroup$
    – Kaveh
    Jan 11, 2016 at 13:24
  • $\begingroup$ It is not an exercise. As a side project I am implementing a small functional language for embedded systems (with some verification/security feats). While thinking about the core langage this question arose.. $\endgroup$
    – D.F.F
    Jan 11, 2016 at 13:49
  • $\begingroup$ Yes, if your set of initial functions is rich enough that you can implement ordered pairs (including the projection functions). $\endgroup$ Jan 11, 2016 at 14:33
  • $\begingroup$ I use the usual formulation (as given eg. in Wikipedia). So I have (the usual) projection functions but no pairing. I don't see how I could implement pairing without multiplication and I cannot define multiplication. $\endgroup$
    – D.F.F
    Jan 11, 2016 at 14:45


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.