4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – xavierm02 Apr 4 '17 at 10:53
  • $\begingroup$ 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! $\endgroup$ – Sebastian Oberhoff Apr 4 '17 at 13:50
  • $\begingroup$ 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) $\endgroup$ – chi Apr 4 '17 at 14:38
  • $\begingroup$ 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). $\endgroup$ – xavierm02 Apr 4 '17 at 14:43
2
$\begingroup$

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))$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.