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$ – Daniel Gratzer Jan 11 '16 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 '16 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 '16 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$ – Emil Jeřábek Jan 11 '16 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 '16 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.