3
$\begingroup$

Given the recursively defined function $c$: $$c(m,n)=\begin{cases}0&\text{for }m=0\\ n^2+n+1&\text{for }m = 1\text{ and }n\ge 0\\ c(m-1, 1)&\text{for }m>1\text{ and }n=0\\ c(m-1,c(m,n-1))&\text{for }m>1\text{ and }n>0\\ \end{cases}$$

and the function $d$:

$$d(n) = \underbrace{2^{2^{.^{.^{.^{.^{2}}}}}}}_{\text{$n+2$ }}$$

The inputs $m$ and $n$ are both natural numbers. I'm asked to find an $x$, such that for all numbers $y \ge x$, $c(y,y) > d(y)$.

I rewrote the two functions using Python in order to calculate some values:

 c(m, n):
    if m == 0:
        return 0
    else if m == 1 and n >= 0:
        return n**2+n+1              # return n^2+n+1
    else if m > 1 and n == 0:
        return c(m-1, 1)
    else if m > 1 and n > 0:
        return c(m-1, c(m, n-1))

 d(n):
    exp_num = n-1
    result = 2
    while exp_num != -1:
        result = 2**result           # result = 2^result
        exp_num = exp_num - 1
    final_result = 2**result         # final_result = 2^result
    return final_result

Some inputs and outputs:

c(1, 1) = 3

c(2, 2) = 183

d(1) = 16

d(2) = 65536

d(3) = 20035299... 19156736, a number with 19729 digits.

I believe the threshold is $3$, as c(3, 3) doesn't seem to be realistically computable considering there are over 19K digit in A(4, 2). Unfortunately I have no idea how to prove this. Any help would be much appreciated.

$\endgroup$
  • $\begingroup$ Look up the Ackermann function for more details $\endgroup$ – narek Bojikian Dec 28 '19 at 6:10
2
$\begingroup$

As you suspected, the threshold is indeed 3.

Here is one approach to prove that for all numbers $y \ge 3$, $c(y,y) > d(y)$.

Step 0, show that $c(\cdot, \cdot)$ is strictly increasing with respect to each variable when the second variable is not 0.
Step 1, show that $c(1,n) \gt n^2$ for all $n\ge0$.
Step 2, show that $c(2,n) \gt 2^n$ for all $n\ge0$.
Step 3, show that $c(3,n)\gt d(n)$ for all $n\ge0$.
Step 4, show that $c(y,y) \gt d(y)\text{ if }y\ge3$.


Exercise. Show that $c(3,y) > \underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{2y+2 \text{ copies of }2}$ for all $y\ge0$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for answering, I could show that c is monotone increasing, but could you elaborate why 1, 2, 3 are necessary? $\endgroup$ – iMazing Dec 27 '19 at 10:42
  • $\begingroup$ I also edited my Python implementation of d(n) $\endgroup$ – iMazing Dec 27 '19 at 10:59
  • $\begingroup$ "Could you elaborate why 1, 2, 3 are necessary?" I am not sure of what you were asking. They are just part of my approach to prove 3 is the threshold. Each of them can be proved by simple induction using what have been proved in previous steps. $\endgroup$ – John L. Dec 27 '19 at 14:05
  • $\begingroup$ I wasn't sure why we had prove the previous steps. Thank you, I will try to solve and get back to you later today. $\endgroup$ – iMazing Dec 27 '19 at 15:47
  • $\begingroup$ I'm having some trouble proving 3. After using the induction hypothesis and the result from 2, I end up at 2^(2^c(3,n)) > d(n+1). Why does this hold? I know that c(3,n) > d(n) (induction hypothesis) but that's about it. $\endgroup$ – iMazing Dec 27 '19 at 17:24

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.