# How can primitive recursion in two variables be made to be of only one variable?

Problem 7.16 in The Nature of Computation reads as follows:

[...] show that when defining primitive recursive functions, we really only need to think about functions of a single variable. In particular, show that a function $f(x)$ is primitive recursive if and only if it can be generated from $0$, $S$, $pair$, $left$, and $right$, using composition and iteration, where iteration is defined as follows: if $f(x)$ and $g(x)$ are already defined, we can define a new function $h(y)=g^y(f(0))$. In fact, we can simplify this further and just take $h(y)=g^y(0)$.

($S$ is the successor function. $pair$, $left$, and $right$ create a tuple and take it apart again.)

It's easy to see that one can use $pair$, $left$, and $right$ to put multiple arguments into a tuple, pass that to a function and have that function extract the arguments back out. Similarly a recursive function of the form $f(x) = g(x,f(x-1))$ can be replaced by $f(x) = h^x(0)$. ($h$ will have to return a tuple $(x, f(x-1))$).
However I'm unable to deal with the case where multiple parameters and recursion occur simultaneously, i.e. $f(x,y)=g(x,f(x,y-1))$. The trouble occurs before trying to replace the recursion by iteration, at the stage where multiple arguments have to be combined. The problem is that, the way I see it, primitive recursion is only allowed to call the immediately next smaller case. For instance, $f(64)$ can call $f(63)$, but not $f(32)$. But $pair(x,y-1)\neq pair(x,y)-1$. So when calling a recursive function with a tuple, it can't access the corresponding smaller case that it would've had access to in the multi-parameter setting.

For reference: $pair$ is defined similar to how the rationals are put in a one-to-one correspondence to the natural numbers by Cantor's argument. Though instead of snaking back and forth along the diagonals, it always moves along a diagonal in the same direction, starting over when reaching the end of one.

• You can encode lists using primitive recursive functions. So you can return a list of all values on smaller inputs, in some organized order, instead of just the value. – xavierm02 Apr 4 '17 at 10:53
• I can see how that might work for most values but suppose I call a primitive recursive function $f$ with the value $6$, which is $(3,0)$ disguised with the $pair$ function. If the original multi-variable function $f(x,y)$ recurses in the second variable this is supposed to be a base case. But $f(6)$ has no way of knowing that. It'll try to call $f(5)$ which is corresponds to $f(0,2)$. Even if you pass on the burden of computing the base case, $f(0,2)$ and the calls below will have no idea that $x$ was $3$ when the base case was originally hit. But that's crucial information! – Sebastian Oberhoff Apr 4 '17 at 13:50
• Rephrasing what xavierm02 suggested. For any $f(x,y)$, define $F(x,y)$ to be the encoding of the list $(0,0,f(0,0)),(1,0,f(1,0)), (0,1,f(0,1)),\ldots,(x,y,f(x,y))$ following your ordering. You should be able to define $F(p)$ in terms of $F(p-1)$ since the latter contains all the possible recursive calls (at the moment, I'm unsure about how to this with the above liminations) – chi Apr 4 '17 at 14:38
• I've added an answer because it didn't fit in comments. Your order on pairs isn't a problem because, up to a primitive recursive bijection whose inverse is also primitive recursive, it's (a suborder of) the usual order on $\mathbb N$. And then, one you have changed the order, you can just remember all computed values in a list (even though since the lists will be indexed with the other order there may be a few things to adjust). – xavierm02 Apr 4 '17 at 14:43

A few facts that should help:

1 - You can encode lists with primitive recursive functions

I can expand if needed.

I'll write lists as $[x_1, \dots, x_n]$, write $x::[x_1,\dots ,x_n]$ for $[x,x_1,\dots,x_n]$ and $\operatorname{hd}([x_1,\dots ,x_n])$ for $x_1$.

2 - You can use any order you want when defining a function by primitive recursion

Let $b$ be a primitive recursive bijection whose inverse is also primitive recursive. Then you can use recursion with respect to the order $x<_by$ defined as $b(x)<b(y)$ and it will still define primitive recursive functions. Suppose that you have $g(x,b(0))=g_0(x)$ and $g(x,b(k+1))=h(x,b(k),g(x,b(k)))$. Then you can define $g'(x,0):= g_0(x)$ and $g'(x,k+1)=h(x,b(k),g'(x,k))$ and you will get $g'(x,k)=g(x,b(k))$ so that you can now define $g(x,y):=g'(x,b^{-1}(y))$.

3 - Your function can know its value on all smaller inputs when defining a function by primitive recursion

Let $X$ be the domain of your function $g$ defined by $g(x,0)=g_0(x)$ and $g(x,k+1)=h(x,k,[g(x,k),g(x,k-1),\dots,g(x,0)])$. Then you can define $g'(x,0):=[g_0(x)]$ and $g(x,k+1):=h(x,k,g'(x,k))::g'(x,k)$ and you will have $g'(x,k)=[g(x,k),g(x,k-1),\dots,g(x,0)]$. You can therefore define $g(x,k):=\operatorname{hd}(g'(x,k))$.