5
$\begingroup$

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$

and

$\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. .

  • 0
    (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.2011-04-03

2 Answers 2

1

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. ...

3

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))$

  • 0
    @ temo : Ok it is not that easy. What you are trying to prove is a refinement on the proof that Ackermann is not primitive recursive. My invariant cannot work because I lose way too much efficiency compared to the original proof. I can't think of a good correction to make. Maybe we should prove that Ack(n,0) grows faster than any Ack(m,n) for any constant m.2011-04-03