Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Primitive recursive

  1. Feb 5, 2005 #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":
    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. jcsd
  3. Feb 6, 2005 #2
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook