My function is $f:\mathbb{N} \rightarrow \mathbb{N},\ f(n)=2\uparrow ^n 3$ , the Ackermann(-Péter) function, with the second argument fixed to 3 (and "$\uparrow$" the Knuth up-arrow), which I believe is not primitive recursive, but which I could not prove - and that is what this question is about. Any ideas for the proof are very welcome.


Idea 1 I have tried to prove that it is not primitive recursive in the lines of the proof that the Ackermann function is not primitive recursive - meaning I tried to prove, that my function $f$ bounds in some way all the other primitive recursive functions, so that I arrive at a contradiction, if I assume, that $f$ would be primitive recursive, because than it would bound itself. The way in which I tried to prove, that $f$ should bound all the other functions was: If $g$ is an arbitrary primitive recursive $k$-ary function $g:\mathbb{N}^k \rightarrow \mathbb{N}$, than there exists an natural number $N$, such that for all $n_1 , ..., n_k > N$ we get $ g(n_1, ... ,n_k) < f(n_1 + ... +n_k)$.

I thought I could try to prove this by trying to prove, that the set of all primitive recursive functions, which are bounded by f like described above, fulfills the properties which the primitive functions have to fulfill (the "standart" functions belong to this set, the set is closed under composition, the set is closed under primitive recursion). Since the primitive recursive functions are the smallest set, that fulfills these properties, I would obtain that this set has to equal the set of all the primitive recursive functions, which would the give me my contradiction. But this proof failed as well, because I can't show, that this set is closed under composition - that is, I can't show that given functions $h:\mathbb{N}^l \rightarrow \mathbb{N}$ and $g:\mathbb{N}^k \rightarrow \mathbb{N}$, which have the property, that:

$\exists N_1 \ \forall n_1,\ldots,n_{l}>N_1$ such that $h(n_1 ,\ldots ,n_{l})<2 \uparrow^{n_1 + \ldots + n_{l}} 3$


$\forall i \in $ {$ 1,\ldots,l $}$ \ \exists N_{i+1} \ \forall n_1,\ldots, n_{k} > N_{i+1} $ such that $g_i(n_1, \ldots ,n_{k})<2 \uparrow^{n_1 + \ldots + n_{k}} 3$

then there should exists an $N$ such that $\forall n_1,\ldots,n_{k}>N$ we should also have, that $t(n_1,\ldots,n_k):=f(g_1(n_1,\ldots ,n_k),\ldots ,g_l(n_1,\ldots,n_k))<2 \uparrow^{n_1 + \ldots + n_{k}} 3$.

In trying to prove the this, I somehow have to make use of the above properties of the functions $g_i$ and $h$. But I can't use the "boundedness" of $h$ because I can't control how much the functions $g_i$ grow - if there aren't values $n_1,\ldots ,n_k$ such that each of the $g_i$'s grow above $N_1$, then I can't make use of $h$'s properties. Maybe there is some other way to prove the closedness under composition, but I can't see it.

Idea 2

I have tried, to proceed indirectly and to assume, that my $f$ would be primitive recursive - the idea was to construct out of this now primitive recursive $f$ another primitive recursive function, that would violate the "Ackermann"-bound - in the sense of the original proof, where one proves that the Ackermann function is not primitive recursive, by first establishing this "Ackermann" bound which all primitive recursive functions have to obey and then showing, that if the Ackermann function is assumend to be primitive recursive one obatains a contradiction.

Could anyone please give me an idea how to finish one of this proof ?


1 Answer 1


I believe one proof technique was to use a primitive recursive encoding of multiple argument functions, so that it would suffice to show a bound on a composition of unary primitive recursive functions. You might try first showing that your function bounds any unary primitive recursive function first.

Gerhard "Ask Me About System Design" Paseman, 2011.04.03


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.