Primitive Recursive Proof in Davis, Sigal & Weyuker Textbook

  • Context: Graduate 
  • Thread starter Thread starter gnome
  • Start date Start date
  • Tags Tags
    Primitive
Click For Summary
SUMMARY

The discussion centers on the proof of the function f(x, y) = x + y as presented in the textbook "Computability, Complexity and Languages" by Davis, Sigal, and Weyuker. The proof utilizes primitive recursive functions u, s, and g, with g defined as g(x_1, x_2, x_3) = s(u_2^3(x_1, x_2, x_3)). The participant questions whether a simpler formulation of f using s(f(x, y)) instead of g is equally valid. The conversation highlights that the textbook's proof aligns with their specific definition of recursion, which may not be universally applicable to all proofs involving recursion.

PREREQUISITES
  • Understanding of primitive recursive functions
  • Familiarity with the definitions of recursion in formal mathematics
  • Knowledge of the functions u and s as defined in the context of the textbook
  • Basic comprehension of mathematical proofs and notation
NEXT STEPS
  • Study the concept of primitive recursion in detail
  • Examine the definitions of recursion in various mathematical texts
  • Explore alternative formulations of recursive functions
  • Review the implications of different definitions of recursion on proofs
USEFUL FOR

Mathematicians, computer scientists, and students studying computability and complexity who are interested in understanding the nuances of recursive function definitions and their applications in formal proofs.

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.
 

Similar threads

  • · Replies 4 ·
Replies
4
Views
1K
  • · Replies 2 ·
Replies
2
Views
3K
  • · Replies 2 ·
Replies
2
Views
3K
  • · Replies 6 ·
Replies
6
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K
Replies
3
Views
2K
  • · Replies 5 ·
Replies
5
Views
3K
  • · Replies 1 ·
Replies
1
Views
3K
  • · Replies 12 ·
Replies
12
Views
4K
  • · Replies 6 ·
Replies
6
Views
3K