computation.
EXERCISES
1. Use the definitions in Examples 13.1 and 13.2 to prove that 3 + 4 = 7 and 2 *
3 = 6.
2. Define the function
greater(x,y) = 1 if x > y,
= 0 if x ≤ y.
Show that this function is primitive recursive.
3. Consider the function
equals (x, y) = 1 if x = y,
= 0 if x ≠ y.
Show that this function is primitive recursive.
4. Let f be defined by
f(x, y) = x if x = y,
= 0 if x = y.
Show that this function is primitive recursive.
* 5. Integer division can be defined by two functions div and rem:
div (x, y) = n,
where n is the largest integer such that x ≥ ny, and
rem (x, y) = x – ny.
Show that the functions div and rem are primitive recursive.