Let $t \in \mathbb{N}$ and consider the function $f: \mathbb{N} \rightarrow \mathbb{N}$, defined by $f_t (m)= 2 \uparrow^{m} t$,

where "$\uparrow$" is Knuth's up-arrow notation (which can be recursively defined - as I can't seem to come up quickly with an online reference for this recursive definition - by $x\uparrow^{0}t=x\cdot t,\ x\uparrow^{m}0=1$ (if $m \neq 0$), $\ x\uparrow^{m+1}\left(t+1\right)=x\uparrow^{m}\left(x\uparrow^{m+1}t\right)$)

My question is, whether this function is primitive recursive for all $t \in \mathbb{N}$. For the values $t=0,1 \dots$ we get $f_0 (m)=$ sgn$(x)$, $f_1 (m)=x\uparrow^{m} 1,\ \dots $ so my guess is, since these are primitive recursive functions, that it be primitive recursive for all $t \in \mathbb{N}$.

(It seems obvious that a proof by induction is required, but I can't seem to figure out the induction step:

Supposing that $f_t (m)$ is primitive recursive, then we have to show that $f_{t+1} (m) $ is primitive recursive as well. My idea was to show this by using the definition of primitive recursive functions, i.e. by using primitive recursion:

$f_{t+1} (0)= 1 $ which is primitive recursive.

$f_{t+1} (m+1)= 2 \uparrow^{m+1} (t+1)=2 \uparrow^{m} (2 \uparrow^{m+1} t)$, but the problem is that I can't use the induction hypothesis to show that $2 \uparrow^{m} (2 \uparrow^{m+1} t)$ is a primitive recursive function, since $ (2 \uparrow^{m+1} t)>t$.)

Any help would be much appreciated.

EDIT (In response to chandok's answer; because this wouldn't have fitted in the comments):

Sorry, that I still haven't got it, but I am not sure, if I can modify the proof that the Ackermann function is not primitive recursive, to suit the needs for my function $f_3$. If I want to prove the closedness under composition - that is, 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 \left\{1,\ldots,l \right\} \ \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$

i run into problems: In trying to prove the above statement, I somehow have to make use of the above properties. But I can't use the "boudedness" of $h$ because, 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. .

  • $\begingroup$ The Wikipedia page on up-arrow notation states that your function is a shifted version of Ackermann's function under the section "Computing $2 \uparrow ^m n$ $\endgroup$ – Ross Millikan Apr 3 '11 at 15:40
  • $\begingroup$ I am not quite sure, if I understood this correctly, but my function is unary, whereas Ackermanns function is binary ( If I fix the argument $n$ to some value in Ackermanns function I would of course get my function $f_n$. But I don't know how this would help to finish the proof). $\endgroup$ – temo Apr 3 '11 at 15:59
  • 2
    $\begingroup$ But the culprit in his function is the first argument, which is your $m$. Your $f_t(m)$ is $A(m+2,t-3)+3$. For fixed $m$, $A(m,n)$ is primitive recursive-it is just when you allow $m$ to increase that it fails. $\endgroup$ – Ross Millikan Apr 3 '11 at 16:09
  • $\begingroup$ I see your point (at least I think I do). But it still amounts to proving, that $A(m+1,t-3)+3$ is not primitive recursive, for some fixed $t\geqslant 3$. I have looked by now a dozen times I think at the proof that the Ackermann functions is not primitive recursive, but I can't see - if I would attempt an indirect proof, and assume that, for example $f_3$ would be primitive recursive - how I could create out of my function $f_3$, which is now presumed to be primitive recursive, another primitive recursive function, that would violate the "Ackermann" bound. $\endgroup$ – temo Apr 3 '11 at 16:23
  • $\begingroup$ (maybe I should have explained in greater detail the "Ackermann" bound)....The above statement 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 obtains a contradiction, since it violates its own bound. $\endgroup$ – temo Apr 3 '11 at 17:15

For any $t \ge 3$, your function $f_t$ is not primitive recursive.

You can probably prove that the same way as Ackermann's function : Prove by induction that for any $k$-ary recursive primitive function $f$, you have $\forall t \ge 3, \exists n, \forall n_1 \ldots n_k, (n_1 + \ldots + n_k \ge n \implies f(n_1,\ldots n_k) \lt f_t(n_1 + \ldots + n_k))$

  • $\begingroup$ I tried to use your idea for a proof (specifically to prove, that $f_3$ is not primitive recursive), but I am not sure, if it could work, because in the induction step $k \mapsto k+1$, I have to prove, that the above holds for any $k+1$-ary function - meaning for every $k+1$-ary function I have to have $\exists n \in \mathbb{N}, \forall n_1 , \ldots , n_{k+1} ( n_1 , \ldots , n_{k+1} \geqslant n \Rightarrow f( n_1 , \ldots , n_{k+1}) < 2 \uparrow ^{( n_1 + \ldots +n_{k+1})}3)$. [I'll continue in the next comment, because I've run out of characters in this one] $\endgroup$ – temo Apr 3 '11 at 7:54
  • $\begingroup$ Now for every $n_{k+1} \in \mathbb{N}$ I can obtain, using the induction hypothesis, that there exists an $n\in \mathbb{N}$ such that the $k$-ary function, that corresponds to the function $f(n_1),\ldots,n_{k},n_{k+1}$, with $n_{k+1} fixed$. But my problem is, that by this procedure I have no means to extract from all the $n$'s I have obtained for all the $n_{k+1}$'s one that will every $n_{k+1}$ (the $n$'s might be increasing, so I am not able to take a maximum). $\endgroup$ – temo Apr 3 '11 at 8:02
  • $\begingroup$ (...one that will bound $f$ for every $n_{k+1}$ that is...sorry for the typo) $\endgroup$ – temo Apr 3 '11 at 8:40
  • $\begingroup$ The induction is not about the integer $k$, it's about the primitive recursive functions $f$. Google tells me this about Ackermann's function : home.manhattan.edu/~gregory.taylor/thcomp/pdf-files/… Look at Lemma 6 specifically. $\endgroup$ – mercio Apr 3 '11 at 8:46
  • $\begingroup$ (I've responded as an edit in my question to the comments) $\endgroup$ – temo Apr 3 '11 at 19:28

Ok I,ve finally solved it, thanks to a hint (namely to apply the lemma) someone gave me. The solution is rather short, if we have this additional lemma at hand:

Lemma: $\forall y\geqslant3 \ \forall n \in \mathbb{N}: 2\uparrow^{n+1} y\geqslant 2 \uparrow^n (y+1)$

This can be easily proved by an induction.

What I will prove now, is that $2 \uparrow^n 4$ is not primitive recursive (from now on abbreviated as "p.r."): Suppose $2 \uparrow^n 4$ would be p.r. Then $2 \uparrow^{2n} 4$ is also p.r. as a composition of p.r. functions.

If we think back to the proof, that the Ackermann function is not p.r., we can remember that we had this bound, that every p.r. function had to fulfill, namely (in our case now):

$\exists N \in \mathbb{N} \ \forall n \geqslant N: \ 2 \uparrow^{2n} 4 \leqslant 2 \uparrow ^N (n+3)$.

Choose $n=N$. We then have $ 2 \uparrow^{2N} 4 \leqslant 2 \uparrow^N (N+3)$.

Apply the above lemma $N$ times, to get:

$ 2 \uparrow^{N} (N+4) \leqslant 2 \uparrow^{2N} 4 \leqslant 2 \uparrow^N (N+3)$. Contradiction, because $ 2 \uparrow^{N} (N+4) > 2 \uparrow^N (N+3)$.

Im still amazed (and slighty annoyed) how much time I spent on this problem and how short it was, in the end...

P.S. I would still be interested, if someone had a different proof, maybe by managing to modify nonetheless the proof that the Ackermann function isn't p.r. ...


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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