Ackermann function

find $A(1, y)$ and $A(2, y)$ for all natural numbers $y$;

prove that $A(3, y)=2^{y+3}-3$.

Find $A(1, y)$ and $A(2, y)$ for all natural $y$.

Prove that $A(3, y)=2^{y+3}-3$.

Prove that the Ackermann function is general recursive. Hint. Using the functions $K$ and $K^{\prime }$ (Problem 581 on the facing page), construct sequences $(x_{1}, x_{2}, \ldots , x_{n}, z)$ such that $\circledast$

Let $A_{m}(n)=A(m, n)$. What is $A_{2}(n)$? $A_{3}(n)$? Show that each $A_{m}$ is primitive recursive.

Show that $A$ is a recursive function.

Show that for every primitive recursive function $f: \mathbf{N} \rightarrow \mathbf{N}$, there exists an integer $k \geq 0$ such that $f(n) \leq A_{k}(n)$ for almost all $n \geq 0$ (i.e., for all but finitely many $n \geq 0$).

Show that $A$ is not primitive recursive.

Compare the function $f(n)=A(n, n)$ with $2^{2^{n}}$.

Compare the function $g(n)=\max \left\{ k \mid A(k, k) \leq n\right\}$ with $\log^{*} n$.

$B(x, y)$ and $A(x)$ are general recursive;

$B(n+2, x+1) \geq 2^{x+1}$;

$B(n+1, x+2) \geq B(n+1, x+1)$;

$B(n+2, x+3) \geq B(n+1, x+4)$;

the simplest functions are $B$-majorized;

a function obtained by means of superposition from $B$-majorized functions is $B$-majorized;

a function obtained by means of primitive recursion from $B$-majorized functions is $B$-majorized;

the function $A$ is not primitive recursive.