There are a couple of questions here which show that the modern Ackermann function $A(i, x)$ is not primitive recursive. This new Ackermann function defined by Péter is a simplification of the original function proposed by Ackermann. I want to show that this original function is not primitive recursive. Unfortunately, the original paper is only in German (from what I could find) so I set about to try it myself.
He defines the function but the following double recursion.
$$\begin{cases}
\zeta(0,b,a) = a+b \\
\zeta(n', 0, a) = \alpha(n,a)\\
\zeta(n',b', a) = \zeta(n,\zeta(n',b,a),a)
\end{cases}$$
where
$$\hspace{-.75in}\alpha(n,a) =
\begin{cases}
0 \,\,\,\,\text{if}\,\,n= 0\\
1\,\,\,\,\text{if}\,\,n =1\\
a\,\,\,\,\text{otherwise}
\end{cases}.$$
For example, $\zeta(0,b,a)=a+b$, $\,\,\,\,\zeta(1,b,a)=ab$, $\,\,\,\,\zeta(2,b,a)=a^b$, $\,\,\,\,\zeta(3,b,a)=a^{a^{a^{a}}}$, with $b$ exponents. This creates a sequence of functions, iterating over $n$, each that grow fast than the functions that come before.
Now the proofs for the modern Ackermann function go like this. Define a set $D$ of number theoretic functions that are dominated by the function $A(i,x)$. Usually it looks like $D = \{\phi:\exists t \,\,\text{s.t.}\,\, \phi(x_1, …,x_n) < A(t, \max(x_k))\}$. Then show that the successor function, the constant functions and the identity functions are in $D$. Lastly show that $D$ is closed under both schemata of primitive recursion. Then $D$ contains every primitive recursive function and if $A(i,x)$ were primitive recursive, it would dominate itself which is absurd.
I'm mainly wondering how I would define $D$ for the function given above. I started by defining $\zeta(a) = \zeta(a, a, a).$ This function $\zeta(a)$ then gives me the $a$th iteration of the sequence of functions with $a,a$ as arguments. Then I tried the sets
$$D=\{\phi: \exists t \,\,\text{s.t.}\,\,\forall x_k > t, \phi(x_1,…,x_n) < \zeta(\max(x_k))\} \tag{1}$$
and
$$D=\{\phi: \exists t,\,\,\exists x_k > t\,\,\text{s.t.}\,\, \phi(x_1,…,x_n) < \zeta(\max(x_k))\}. \tag{2}$$
However, with $(1)$ I couldn't show that $D$ was closed under the composition of functions schema, and with $(2)$ I couldn't show that the identity function, $\phi(x_1,…,x_n) = x_k$ for some $k=1, …,n$ was a necessarily in $D$. My question is, what kind of $D$ should I set up to show it is closed under primitive recursive schema?
Best Answer
This is simply a recursive definition of hyperoperators (Knuth's up-arrow notation), and so it satisfies the relation
$$A(m,n)=\zeta(m-2,2,n+3)-3$$
with the Ackermann function. From this the same proof can be used.