@vzn I have chosen the Ackermann's function for the presentation...


I am reading the definitions of primitive recursive functions and recursive functions.

The definition of $\mu-$recursive functions is the following:
1. The constant, projection, and successor functions are all $\mu-$recursive.
2. If $g_1, \dots , g_m$ are $n-$variable $\mu-$recursive functions and $h$ is an $m-$variable $\mu-$recursive function, then the composite function $f=h \circ (g_1, \dots , g_m)$ is also $\mu-$recursive.

@vzn I thought that the structure of the presentation will be the following:

-History
-Definition (I mention the original version of the function and the simplified version of Rozsa Peter)
-Table of some values of the function and mention that it grows so fast that even for small inputs it gives huge results
-Definition of primitive recursive functions
-Proof that Ackermann's function is not primitive recursive
-Definition of recursive functions
-Proof that Ackermann's function is recursive/Turing-computable

In the book that I am reading there is the following proof:

To prove that Ackermann's function is not primitive recursive, we need the following properties concerning the values of $A$.

1. $A(x,y)>y$.

2. $A(x,y+1)>A(x,y)$.

3. If $y_2>y_1$, then $A(x,y_2)>A(x,y_1)$.

4. $A(x+1, y) \geq A(x,y+1)$.

5. $A(x,y)>x$.

6. If $x_2>x_1$, then $A(x_2, y)>A(x_1, y)$.

7. $A(x+2, y)>A(x,2y)$.


We will prove that Ackermann's function is not primitive recursive by showing that it "grows faster" than any primitive recursive function. What we shall attempt to do is show that for any given $n-$variabl…