<p>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)) 
$$</p>

<p>lead to the same class of primitive recursive functions?</p>

CC BY-SA 3.0
2016-01-11T12:32:14.460Z
If you can define products absolutely, otherwise maybe not..
daniel gratzer
CC BY-SA 3.0
2016-01-11T13:24:51.390Z
This looks like an exercise in computability theory. If not please explain why are you interested in this question. Please also check our [help/on-topic] for description of the scope of this site and suggestions for other sites in case your question is off-topic here.
Kaveh
CC BY-SA 3.0
2016-01-11T13:49:46.853Z
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..
D.F.F
CC BY-SA 3.0
2016-01-11T14:33:41.610Z
Yes, if your set of initial functions is rich enough that you can implement ordered pairs (including the projection functions).
Emil Jeřábek
CC BY-SA 3.0
2016-01-11T14:45:58.553Z
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.
D.F.F
<recursion>
Omitting parameters in primitive recursive functions
D.F.F
# Omitting parameters in primitive recursive functions

(Asked by: username_0 on 2016-01-11)

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?

**Tags:** recursion
> **Comments:**
> **username_1**: If you can define products absolutely, otherwise maybe not..  
> **username_2**: This looks like an exercise in computability theory. If not please explain why are you interested in this question. Please also check our [help/on-topic] for description of the scope of this site and suggestions for other sites in case your question is off-topic here.  
> **username_0**: 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..  
> **username_3**: Yes, if your set of initial functions is rich enough that you can implement ordered pairs (including the projection functions).  
> **username_0**: 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.  

---

## 0 answers

