I've implemented the following two functions in Python:
def c(m, n):
if m == 0:
return 0
elif m == 1 and n >= 0:
return n**2+n+1
elif m > 1 and n == 0:
return c(m-1, 1)
elif m > 1 and n > 0:
return c(m-1, c(m, n-1))
def d(n):
exp_num = n-1
result = 2
while exp_num != -1:
result = result**2
exp_num -= 1
final_result = 2**result
return final_result
Where the inputs m and n are both natural numbers. I'm asked to find an x, such that for all numbers y >= x, c(y,y) > d(y).
Some inputs and outputs:
c(1, 1) = 3
c(2, 2) = 183
d(1) = 16
d(2) = 65536
d(3) = 115792089237316195423570985008687907853269984665640564039457584007913129639936
As you can see d grows extremely faster than c. How can I approach this problem? Any help would be much appreciated.
The function c is a variant of Ackermann–Péter function.
It claims to fame is that it is not Primitive Recursive which for purposes here means it quickly runs out of stack space in its computation as the numbers become very large.
The problem is to find min x, such that c(y, y) > d(y), for y >= x.
We believe this is c(3, 3) but it can't be computed. We did compute for 1 & 2:
d(1) = 16, d(2) = 65536, d(3) = 115792089237316195423570985008687907853269984665640564039457584007913129639936
c(1) = 3, c(2, 2) = 183, c(3, 3) = ?
Because it's not primitively-recursive, c(3, 3) is difficult to compute (i.e. run out of stack space). However, rather than an exact number, we can obtain a lower-bound by by limiting the recursions in the function definition.
This is done as follows.
# Will use Memoization which eliminates repeated calculations in recursive functions
class Memoize:
def __init__(self, fn):
self.fn = fn
self.memo = {}
def __call__(self, *args):
if args not in self.memo:
self.memo[args] = self.fn(*args)
return self.memo[args]
@Memoize
def c(m, n, cnt = 0, MAX_RECURSION = 20):
" Refactor function c to have a max recursion depth "
if cnt > MAX_RECURSION:
return 0 # We know the return value is always >= 0, but normally
# much larger. By quitting early and returning zero we are
# ensuring our final computation will be smaller than it would
# otherwise if we had not limited the recurison depth
#
if m == 0:
return 0
elif m == 1 and n >= 0:
return n**2+n+1
elif m > 1 and n == 0:
return c(m-1, 1, cnt+1)
elif m > 1 and n > 0:
return c(m-1, c(m, n-1, cnt+1), cnt+1)
def d(n):
exp_num = n-1
result = 2
while exp_num != -1:
result = result**2
exp_num -= 1
final_result = 2**result
return final_result
value_d = d(3)
value_c = c(3, 3)
print('Number of digits in d(3) is {}'.format(len(str(value_d))))
#>>> Number of digits in d(3) is 78
print('Number of digits in c(3, 3) is {}'.format(len(str(value_c))))
#>>>Number of digits in c(3, 3) is 74176
Thus, we see that c(3, 3) has ~1K more digits than d(3). It will be even more since we stopped the recursion early in computing c(3, 3).