A recursive function is defined by a finite set of rules that specify the function in terms of variables,

nonnegative integer constants, increment $(\text{'}+1\text{'}),$ the function itself, or an expression built from these by

composition of functions. As an example, consider Ackermann's function defined as A$($n$)=$ An

$($n$)$ for n $>=1,$

where Ak$($n$)$ is determined by

Ak$(1)=2$ for k $>=1$

A$1($n$)=$ A$1($n$1)+2$ for n $>=2$

Ak$($n$)=$ Ak$1($Ak$($n$1))$ for k $>=2$

$($a$)$ Calculate A$(1),$ A$(2),$ A$(3),$ A$(4).$

$($b$)$ Prove that

Ak$(2)=4$ for k $>=1,$

A$1($n$)=2$n for n $>=1,$

A$2($n$)=2$n

for n $>=1,$

A$3($n$)=2$A

$3$

$($n$1)$ for n $>=2.$

$($c$)$ Define the inverse of Ackermann's function as

$\backslash$alpha $($n$)=$ min$\{$m: A$($m$)>=$ n$\}.$

Show that $\backslash$alpha $($n$)<=3$ for n $<=16,$ that $\backslash$alpha $($n$)<=4$ for n at most a "tower" of $655362\text{'}$s$,$ and that $\backslash$alpha $($n$)->\backslash$infty as n

$->\backslash$infty $.$