I have to read again about Knuth's up-arrow notation to understand it better.
After the part History of the post #5 could I write it the collary ? (The part of the Knuth's up-arrow notation will have to be added)
Ackermann's original function is the mapping $\phi : \mathbb{N}^3 \rightarrow \mathbb{N}$ which is defined recursively as follows:
$$\phi(a,b,0)=a+b \\ \phi(a,0,n+1)=\alpha (a,n) \\ \phi(a,b+1, n+1)=\phi(a, \phi(a,b,n+1),n) \\ \text{ where }\alpha(a,n)=\left\{\begin{matrix}
0 & , n=0\\
1 & , n=1\\
a & , n>1
\end{matrix}\right.$$
The simplified form of Rozsa Peter, which is today known as the Ackermann's function, is the mapping $A: \mathbb{N}^2 \rightarrow \mathbb{N}$ which is defined recursively as follows:
$$A(m,n)\left\{\begin{matrix}
n+1 & , m=0\\
A(m-1,1) & , m>0 , n=0\\
A(m-1,A(m,n-1))& ,m>0,n>0
\end{matrix}\right.$$ Ackermann's function grows astronishingly fast, as we can see at the table of values:
$$ \begin{matrix}
m \setminus n & | & 0 & 1 & 2 & 3 & 4 & 5 & \dots & y \\
- & - & -& - & - & - & - & - & - \\
0 & | & 1 & 2 & 3 & 4 & 5 & 6 & \dots & y+1 \\
1 & | & 2 & 3 & 4 & 5 & 6 & 7 & \dots & y+2 \\
2 & | & 3 & 5 & 7 & 9 & 11 & 13 & \dots & 2y+3 \\
3 & | & 5 & 13 & 29 & 61 & 125 & 253 & \dots & 8 \cdot 2^{y}-3\\
4 & | & 13 & 65533 & & & & & \dots & 2^{2^{.^{.^.}}^2}-3\\
5 & | & 65533 & & & & & & \dots & \\
\dots & | & & & & & & & \dots &\\
\end{matrix} $$
Even for small inputs the function gives huge results. For example, $A(4,2)$ already has $19.729$ digits! After that, to show that the Ackermann's function is recursive do we have to show that it is $\mu-$recursive?
According to the book that I'm reading, we can define the $\mu-$recursive functions inductively, as foolows:
- The constant, projection, and successor functions are all $\mu-$recursive.
- If $g_1, \dots , g_m$ are $n-$variable $\mu-$recursive functions and $h$ is an $m-$variable $\mu-$recursive function, then teh composite function $f=h \circ (g_1, \dots , g_m)$ is also $\mu-$recursive.
- If $g$ and $h$ are $n-$ and $(n+2)-$variable $\mu-$recursive functions, then the function $f$ defined from $g$ and $h$ by primitive recursion is also $\mu-$recursive.
- If $g$is a total $(n+1)-$variable $\mu-$recursive function, then the function $f$ defined from $g$ by unbounded minimalization is also $\mu-$recursive.
Which is the difference between a recursive and $\mu-$recursive function ? (Wondering) To prove that $A$ is not primitive recursive, we need the following properties concerning the values of $A$.
- $A(x,y)>y$.
- $A(x,y+1)>A(x,y)$.
- If $y_2>y_1$, then $A(x,y_2)>A(x,y_1)$.
- $A(x+1, y) \geq A(x,y+1)$.
- $A(x,y)>x$.
- If $x_2>x_1$, then $A(x_2, y)>A(x_1, y)$.
- $A(x+2, y)>A(x,2y)$.
Thus the value of $A$ is greater than that of either of its arguments, $A$ is strictly monotonic in each argument, and the value of $x$ has a greater influence on the value of $A$ than does the value of $y$.
We will prove that Ackermann's function is not primitive recursive by showing that it "grows faster" than any primitive recursive function. That means that we need a precise way of comparing the "growth rate" of the two-variable function $A$ with that of an arbitrary $n-$variable function. What we shall attempt to do is show that for any given $n-$variable primitive recursive function $f$, there exists a natural number $k$ such that $$A(k, \max (x_1, \dots , x_n)) > f(x_1, \dots , x_n) \tag {*}$$ for all values of $x_1, \dots , x_n$.
The proof is accomplished by induction on the number of compositions and primitive recursions needed to define the function $f$. In order to carry out the induction step of the proof, we need two auxiliary results. The results of these results ensures that if the functions $g_1, \dots , g_m$ and $h$ satisfy $(*)$, so does the function $f$ obtained from $g_1, \dots , g_m$ and $h$ by functional composition.
Lemma 1. Let the $n-$variable function $f=h \circ (g_1, \dots , g_m)$ be obtained from the functions $g_1, \dots , g_m$ and $h$ by composition. Assume the existence of natural numbers $k_1, \dots , k_m$, and $k_0$ such that $$A(k_i, \max (x_1, \dots , x_n)) > g_i (x_1, \dots , x_n) \text{ for } 1 \leq i \leq m\\ \text{ and } \\ A(k_0, \max (y_1, \dots , y_m )) > h(y_1, \dots , y_m)$$ for all $x_1, \dots , x_n$ and $y_1, \dots , y_m$. Define $k$ to be the natural number $\max (k_0, k_1, \dots , k_m)+2$. Then $A(k, \max (x_1, \dots , x_n)) > f(x_1, \dots , x_n)$ for all $x_1, \dots , x_n$.
Lemma 2. Let the $(n+1)-$variable function $f$ be defined by primitive recursion from the $n-$variable function $g$ and the $(n+2)-$variable function $h$, so that $$f(x_1, \dots , x_n, 0)=g(x_1, \dots , x_n) \\ f(x_1, \dots x_n, y+1)=h(x_1, \dots , x_n , y, f(x_1, \dots , x_n, y))$$ Assume the existence of natural numbers $k_g$ and $k_h$ such that $$A(k_g ,\max (x_1, \dots , x_n)) > g(x_1, \dots , x_n) \\ \text{ and } \\ A(k_h, \max (x_1, \dots , x_n , y , z)) > h(x_1, \dots , x_n , y, z)$$ for all $x_1, \dots ,x_n, y$ and $z$. Define $k$ to be the natural number $\max (k_g, k_h)+3$. Then $A(k, \max (x_1, \dots , x_n , y)) > f(x_1, \dots ,x_n , y)$ for all $x_1, \dots , x_n, y$.
Theorem 1. For each $n-$variable primitive recursive function $f$, there exists a natural number $k$ such that $A(k, \max (x_1, \dots , x_n)) > f(x_1, \dots , x_n)$, for all $x_1, \dots , x_n$.
Proof. By iduction on the number of compositions and primitive recursions needed to define $f$. We use $\hat{x}$ to denote $\max (x_1, \dots , x_n)$.
Basis. If the derivation of $f$ requires no compositions or primitive recursions, three cases are possible.
- If $f$ is the constant function whose value is $c$, choose $k=c$. Property $5$ then guarantees that $A(k, \hat {x})=A(c, \hat{x})>c=f(x_1, \dots , x_n)$.
- If $f$ is the projection function whose valuee is $x_i$, choose $k=0$. Then $A(k,\hat{x})=A(0,\hat(x))=\hat(x)+1>x_i=f(x_1, \dots , x_n)$.
- If $f$ is the successor function, choose $k=1$. Then $A(k,x)=A(1,x)>A(0,x)=x+1=f(x)$.
Induction step. Assume the statement of the theorem to be true for all functions requiring $w$ or fewer compositions and primitve recursions. Let $f$ be a function requiring a total of $w+1$ compositions and primitive recursions. Two cases are possible.
- If $f$ is derived from functions $g_1, \dots , g_m$ and $h$ by composition, the induction hypothesis must apply to each of $g_1, \dots , g_m$, and $h$. Lemma $1$ then guarantees the existence of a number $k$ such that $A(k,\hat{x})>f(x_1, \dots , x_n)$.
- If $f$ is derived from the functions $g$ and $h$ by primitive recursion, the induction hypothesis must apply to $g$ and $h$. Lemma $2$ then guarantees the existence of a number $k$ such that $A(k, \hat{x})>f(x_1, \dots , x_n)$.
Theorem $1$ provides a formal expression of the notopn that $A$ "grows faster" than any primitive recursive function. It is now a simple matter to establish:
Theorem 2. Ackermann's function is not primitive recursive.
Proof. Assume that Ackermann's function is primitive recursive. Then according to Theorem 1, there must exist a natral number $k$ such that $$A(k, \max (x,y)) > A(x,y)$$ for all $x$ and $y$ . Setting $x=y=k$ then yields the contradiction $$A(k,k) > A(k,k)$$ from which we conclude that $A$ cannot be primitive recursive.
Is this correct? Could I improve something? (Wondering)
