1
$\begingroup$

I am having trouble understanding the definition of primitive recursion. I would like to have clarification of the definition with simple applications of the definition with examples.

The definition of Primitive Recursion is: $h(x,0)=f(x)$, $h(x,s(y))=g(x,y,h(x,y))$.

The short hand is $h=\Pr[f,g]$.

What exactly does: $h(x,s(y))=g(x,y,h(x,y))$ mean?

The example the book gives is Pr for addition: $s(x,0)=x$, $\text{sum}(x,s(y))=s(\text{sum}(x,y))$. Where s means "successor". I do not understand the example, nor how the example correlates to the definition.

Specifically how does $h(x,s(y))=g(x,y,h(x,y))$ correlate to $\text{sum}(x,s(y))=s(\text{sum}(x,y))$ and what is $\text{sum}(x,s(y))=s(\text{sum}(x,y))$ doing? I'd like to see an example so I can see how the definition works.

1 Answers 1

4

The basic idea of primitive recursion is that the value of $h ( x, y+1 )$ can depend on the history of this function (i.e., the values $h(x,0), h(x,1), \ldots , h(x,y)$). (This is not how it is stated, but it turns out to be an equivalent formulation in the class of recursive functions). If you recall the Fibonacci numbers $F(0) = 0, F(1) = 1, F(n+2) = F(n) + F(n+1)$ you get the basic idea of this history, and how the value of a function at an argument can depend on its value at smaller arguments.

In terms of the "sum" function, note that we have an initial condition, $\mathrm{sum} (x,0) = x.$ As you have noticed, this is not quite formally correct. Instead, we should have a unary function $id$ such that $id(x) = x$ for all $x$, and then $\mathrm{sum} (x,0) = id(x) = x.$

Next we have the recursive element, $\mathrm{sum} ( x, y+1 ) = S ( \mathrm{sum} (x,y) ).$ Again, this is not quite formally correct. Instead we should have a ternary function $S_3$ where $S_3(x,y,z) = S(z)$, and then set $\mathrm{sum} ( x , y+1 ) = S_3 ( x, y, \mathrm{sum} (x,y) ).$ Of course, by our definition of $S_3$ this reduces down to the original formula.

In this manner, $\mathrm{sum}$ is defined via primitive recursion on the functions $id$ and $S_3$. (But this becomes a little bit unreadable, and you will usually see it written out in the manner described in your question.)