1
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .