给定两个函数，找到一个阈值，使一个总是大于另一个

Question

我在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

其中输入 m 和 n 都是自然数。我被要求找到一个 x，这样对于所有数字 y >= x、c(y,y) > d(y).

一些输入和输出：

c(1, 1) = 3

c(2, 2) = 183

d(1) = 16

d(2) = 65536

d(3) = 115792089237316195423570985008687907853269984665640564039457584007913129639936

如您所见，d 的增长速度比 c 快得多。我该如何解决这个问题？任何帮助将非常感激。

Answer 1

函数 c 是 Ackermann–Péter function 的变体。

它之所以出名是因为它不是 Primitive Recursive，这里的目的是指随着数字变得非常大，它在计算中很快运行出栈 space。

问题是找到最小 x，使得 c(y, y) > d(y)，对于 y >= x。

我们认为这是 c(3, 3) 但无法计算。我们计算了 1 和 2：

d(1) = 16，d(2) = 65536，d(3) = 115792089237316195423570985008687907853269984665640564039457584007913129639936

c(1) = 3, c(2, 2) = 183, c(3, 3) = ?

因为它不是原始递归的，所以 c(3, 3) 很难计算（即运行出栈 space）。然而，我们可以获得一个下限，而不是一个确切的数字通过限制函数定义中的递归。

这是按如下方式完成的。

# 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

因此，我们看到 c(3, 3) 比 d(3) 多 ~1K 位数。因为我们在计算 c(3, 3) 的早期就停止了递归，所以会更多。

给定两个函数，找到一个阈值，使一个总是大于另一个

Given two functions, find a threshold such that one is always bigger than the other

python

recursion

proof