Problem 3 - Ackermann's function

Ackermann function $A(x,y)$ is defined as follows.

$$\begin{tabular}{l} $A(0,y) = y + 1$, \\ $A(x+1,0) = A(x,1)$, \\ $A(x+1,y+1) = A(x, A(x+1,y))$. \\ \end{tabular}$$

1.

Compute $A(2,2)$.

2.

Describe briefly the role of Ackermann function in information science.

1.

$A(2,2)$
$=A(1,A(2,1))$
$=A(1,A(1,A(2,0)))$
$=A(1,A(1,A(1,1)))$
$=A(1,A(1,A(0,A(1,0))))$
$=A(1,A(1,A(0,A(0,1))))$
$=A(1,A(1,A(0,2)))$
$=A(1,A(1,3))$
$=A(1,A(0,A(1,2)))$ (a)
$=A(1,A(0,A(0,A(1,1))))$
$=A(1,A(0,A(0,A(0,A(1,0)))))$
$=A(1,A(0,A(0,A(0,A(0,1)))))$
$=A(1,A(0,A(0,A(0,2))))$
$=A(1,A(0,A(0,3)))$
$=A(1,A(0,4))$ (b)
$=A(1,5)$
$=A(0,A(1,4))$
$=A(0,A(0,A(1,3)))$
$=A(0,A(0,A(0,A(1,2))))$
$=A(0,A(0,A(0,4)))$ according to (a) and (b)
$=A(0,A(0,5))$
$=A(0,6))$
$=7$

2.

See [HOP79] for further explanations about the Ackermann's function.