snippetMinor
How can primitive recursion in two variables be made to be of only one variable?
Viewed 0 times
canmaderecursionprimitivetwoonevariableshowvariableonly
Problem
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.
[...] 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.
Solution
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)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))$.
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)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))$.
Context
StackExchange Computer Science Q#72446, answer score: 2
Revisions (0)
No revisions yet.