# Primitive recursive

1. Feb 5, 2005

### gnome

In the Davis, Sigal & Weyuker textbook "Computability, Complexity and Languages" their proof that $f(x) = x + y$ goes like this:
$$\begin{equation*}\begin{split}f(x,0) &= u_1^1(x)\\f(x,y+1) &= g(y,f(x,y),x)\end{split}\end{equation*}$$
where $g(x_1,x_2,x_3) = s(u_2^3(x_1,x_2,x_3))$.

And (I'm paraphrasing now in the interest of brevity) these functions u, s and g are all primitive recursive so therefore f is too.

I'm wondering, would it be equally valid (and simpler) to say
$$\begin{equation*}\begin{split}f(x,0) &= u_1^1(x)\\f(x,y+1) &= s(f(x,y))\end{split}\end{equation*}$$
followed by the same explanation?

Apparently, the reason for the form of their proof is that they defined recursion to be one of these two "things":
and they had to put their proof into the same form as their definition of recursion.

So I guess my question boils down to, is that just their definition of recursion, or is it everybody's?

i.e. does every proof involving recursion have to be in exactly that format?

2. Feb 6, 2005

### CrankFan

That is the standard definition of primitive recursion.

Both of the examples are primitive recursive. The foot note on page 40 indicates that they will agree to call "primitive recursion", "recursion" simply as a convenience, until later.