Why does Davis, Sigal & Weyuker use the more complex form for primitive recursion?

  • Context: Graduate 
  • Thread starter Thread starter gnome
  • Start date Start date
  • Tags Tags
    Primitive
Join the discussion
Registration is free. Ask a follow-up in this thread, or start your own.
1 reply · 2K views
gnome
Messages
1,031
Reaction score
1
In the Davis, Sigal & Weyuker textbook "Computability, Complexity and Languages" their proof that [itex]f(x) = x + y[/itex] goes like this:
[tex]\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*}[/tex]
where [itex]g(x_1,x_2,x_3) = s(u_2^3(x_1,x_2,x_3))[/itex].

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
[tex]\begin{equation*}\begin{split}f(x,0) &= u_1^1(x)\\f(x,y+1) &= s(f(x,y))\end{split}\end{equation*}[/tex]
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":
Either:
[tex]\begin{equation*}\begin{split}h(0) &= k\\h(t+1) &= g(t,h(t))\end{split}\end{equation*}[/tex]
or:
[tex]\begin{equation*}\begin{split}h(x_1,...,x_n,0) &= f(x_1,...,x_n),\\h(x_1,...,x_n,t+1) &= g(t,h(x_1,...,x_n,t),x_1,...,x_n)\end{split}\end{equation*}[/tex]
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?
 
Physics news on Phys.org
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.