Ullman (TOC) Edition 3 Exercise 9.2 Question 2 (Page No. 390 - 391)

Question

In the box "Why 'Recursive'?" in Section $9.2.1$ we suggested that there was a notion of "recursive function" that competed with the Turing machine as a model for what can be computed. In this exercise, we shall explore an example of the recursive-function notation. A recursive function is a function $F$ defined by a finite set of rules. Each rule specifies the value of the function $F$ for certain arguments; the specification can use variables, nonnegative-integer constants, the successor (add one) function, the function $F$ itself,  and expressions built from these by composition of functions. For example,Ackermann's  function is defined by the rules:

1. $A(0,y) = 1$ for any $y\geq0.$
2. $A(1,0) = 1.$
3. $A(x,0) = x+2$ for $x\geq 2.$
4. $A(x+1,y+1)=A(A(x,y+1),y)$ for any $x\geq 0$ and $y\geq 0.$

Answer the following:

1. Evaluate $A(2,1).$
2. What function of $x$ is $A(x,2)$?
3. Evaluate $A(4,3)$.