<p>According to this <a href="https://math.stackexchange.com/a/3320009/119167">excellent answer by Rob Arthan on math.stackexchange</a>, the question was actually already posed by Raphael Robinson in 1947, who referred to this restricted recursion schema as &quot;pure recursion&quot;.  Robinson showed that primitive recursion reduces to pure recursion if one adds the predecessor function to the initial basis and asked, &quot;Can predecessor be defined by substitution and pure
recursion from the identity, zero, and successor functions?&quot;  That open problem was resolved affirmatively in 1967 by M. D. Gladstone, who showed how to define the predecessor function thus proving that pure recursion is equivalent to primitive recursion.</p>
<p>So indeed it seems progress has been made on the conjecture, refuting it about 20 years before it was formulated.</p>

CC BY-SA 4.0
2024-12-07T09:37:28.160Z
2024-12-08T14:26:43.430Z
2024-12-08T14:26:43.430Z
Noam Zeilberger
<p>In &quot;<a href="https://doi.org/10.1145/74074.74089" rel="noreferrer">Primitive Recursion without Implicit Predecessor</a>&quot; (1989), Fischer, Fischer, and Beigel conjecture that the class of iterative functions is a strict subset of the primitive recursive functions, where they define iterative functions as being constructed in the same way as primitive recursive functions, except the primitive recursive operator is replaced by a weaker definition:</p>
<p>Given iterative functions <span class="math-container">$g(x_2,\ldots,x_n)$</span> and <span class="math-container">$h(x_1,\ldots,x_n)$</span>, the function <span class="math-container">$$f(y,x_2,\ldots,x_n) = \begin{cases}g(x_2,\ldots,x_n) &amp; y = 0\\h(f(y-1,x_2,\ldots,x_n),x_2,\ldots,x_n)&amp; y &gt; 0\end{cases}$$</span> is also iterative. Specifically, <span class="math-container">$h$</span> does not have direct access to <span class="math-container">$y$</span> at all.</p>
<p>I find this conjecture surprising, since if <span class="math-container">$f$</span> were allowed to output a pair of values, one of the two in the pair could be <span class="math-container">$y$</span>, thus giving <span class="math-container">$h$</span> access to <span class="math-container">$y$</span>.</p>
<p>Has any progress been made regarding this conjecture?</p>

CC BY-SA 4.0
2024-12-06T14:39:53.137Z
Out of curiosity, how is the factorial $n \mapsto n!$ iterative?
Andrej Bauer
CC BY-SA 4.0
2024-12-07T01:39:47.063Z
This would be possible if one could find iterative pairing and pair-decoding functions $pair(x,y), \pi_1,\pi_2$ with $\pi_i(pair(x_1,x_2)) = x_i$. One could then produce the function $n \mapsto pair(n,n!)$ using a purely iterative construction, and then compose with $\pi_2$. Of course that just raises the question of whether there are iterative pairing/projection functions.
TomKern
CC BY-SA 4.0
2024-12-07T06:40:52.393Z
According to this [excellent answer on math.stackexchange](https://math.stackexchange.com/a/3320009/119167), the question was actually already posed by Raphael Robinson in 1947, who referred to this restricted recursion schema as "pure recursion", and resolved in 1967 by M. D. Gladstone who proved that pure recursion is equivalent to primitive recursion by showing how to define the predecessor function.  So indeed it seems progress has been made on the conjecture, refuting it about 20 years before it was posed.
Noam Zeilberger
CC BY-SA 4.0
2024-12-07T08:42:11.257Z
@NoamZeilberger Can you post that as an answer?
Emil Jeřábek
<recursion>
Are Primitive Recursive Functions Iterative?
TomKern
# Are Primitive Recursive Functions Iterative?

(Asked by: username_0 on 2024-12-05)

In "[Primitive Recursion without Implicit Predecessor](https://doi.org/10.1145/74074.74089)" (1989), Fischer, Fischer, and Beigel conjecture that the class of iterative functions is a strict subset of the primitive recursive functions, where they define iterative functions as being constructed in the same way as primitive recursive functions, except the primitive recursive operator is replaced by a weaker definition:

Given iterative functions $g(x\_2,\ldots,x\_n)$ and $h(x\_1,\ldots,x\_n)$, the function $$f(y,x\_2,\ldots,x\_n) = \begin{cases}g(x\_2,\ldots,x\_n) & y = 0\\h(f(y-1,x\_2,\ldots,x\_n),x\_2,\ldots,x\_n)& y > 0\end{cases}$$ is also iterative. Specifically, $h$ does not have direct access to $y$ at all.

I find this conjecture surprising, since if $f$ were allowed to output a pair of values, one of the two in the pair could be $y$, thus giving $h$ access to $y$.

Has any progress been made regarding this conjecture?

**Tags:** recursion
> **Comments:**
> **username_1**: Out of curiosity, how is the factorial $n \mapsto n!$ iterative?  
> **username_0**: This would be possible if one could find iterative pairing and pair-decoding functions $pair(x,y), \pi_1,\pi_2$ with $\pi_i(pair(x_1,x_2)) = x_i$. One could then produce the function $n \mapsto pair(n,n!)$ using a purely iterative construction, and then compose with $\pi_2$. Of course that just raises the question of whether there are iterative pairing/projection functions.  
> **username_2**: According to this [excellent answer on math.stackexchange](https://math.stackexchange.com/a/3320009/119167), the question was actually already posed by Raphael Robinson in 1947, who referred to this restricted recursion schema as "pure recursion", and resolved in 1967 by M. D. Gladstone who proved that pure recursion is equivalent to primitive recursion by showing how to define the predecessor function.  So indeed it seems progress has been made on the conjecture, refuting it about 20 years before it was posed.  
> **username_3**: @NoamZeilberger Can you post that as an answer?  

---

## 1 answers

### Answer by username_2 on 2024-12-07. Score: 11 | Accepted answer

According to this [excellent answer by Rob Arthan on math.stackexchange](https://math.stackexchange.com/a/3320009/119167), the question was actually already posed by Raphael Robinson in 1947, who referred to this restricted recursion schema as "pure recursion". Robinson showed that primitive recursion reduces to pure recursion if one adds the predecessor function to the initial basis and asked, "Can predecessor be defined by substitution and pure
recursion from the identity, zero, and successor functions?" That open problem was resolved affirmatively in 1967 by M. D. Gladstone, who showed how to define the predecessor function thus proving that pure recursion is equivalent to primitive recursion.

So indeed it seems progress has been made on the conjecture, refuting it about 20 years before it was formulated.


---

