什么技术限制阻止在Python中计算格雷厄姆数？

Question

假设运行此程序的计算机具有无限的内存，我想知道在运行以下内容时Python会在何处中断：

为了好玩，我在Python中实现了超级运算符作为hyperop模块。其中一个例子是Graham数：

def GrahamsNumber():
    # This may take awhile...
    g = 4
    for n in range(1,64+1):
        g = hyperop(g+2)(3,3)
    return g

类hyperop的简化版本如下：

def __init__(self, n):
    self.n = n
    self.lower = hyperop(n - 1)

def _repeat(self, a, b):
    if self.n == 1:
        yield a

    i = 1
    while True:
        yield a
        if i == b:
            break
        i += 1

def __call__(self, a, b):
    return reduce(lambda x, y: self.lower(y, x), self._repeat(a, b))

基本上，该库只是一个递归的右折叠操作，对于 n=1 的基本情况有一个特殊的定义。最初，__call__ 被优美地压缩为：

return reduce(lambda x, y: self.lower(y, x), [a,]*b)

然而，事实证明，你无法创建比C long的大小更大的列表。这是一个有趣的限制，大多数Python程序员在日常工作中可能不会遇到，它启发了以下问题。

在哪里（如果有的话），hyperop 计算将因为 Python 技术限制（具体来说是 2.7.10）而失败？

- Hooked

---

由于“可观测宇宙过小，无法容纳Graham数的普通数字表示法”，因此我的答案是否定的。小建议：如果你不得不以“这是个合理的问题”开始，那么你很可能是错的！ - jonrsharpe

@Hooked 你说的“Python”是指什么？CPython？PyPy？还是其他的？另外，是哪个版本？ - Stefan Pochmann

@jonrsharpe，也许我在评论中过于轻率地说这是一个“合法的问题”。我只是想确认这个问题符合SO的合法标准，即它是客观的（不基于意见），有一个具体的目标并且可以被重现。 - Hooked

@PascalvKooten 说得对，我想我需要选择一个特定的Python版本来使这个问题更具体。让我们在这个问题中确认我正在使用Python 2.7.10，尽管我对任何Python 3的答案都很感兴趣。我会相应地进行编辑。 - Hooked

您可能需要编辑您的问题标题，因为您现在的标题的答案显然是“不”。由于您的问题实际上与格雷厄姆数没有任何关系，而是关于Python的技术限制，如果您重新构思问题以便专注于Python所施加的具体限制，而不是计算格雷厄姆数的目标，您可能会得到更好的回应。Python可能确实有其他像您发现的列表长度限制一样的“隐藏”限制，但是您特定的程序可能不会达到这些限制。 - BrenBarn

Answer 1

也许原始版本的hyperop很强大，因为某些奇怪的原因而失败，但是这个精确的代码失败了，因为hyperop构造函数调用它自己，并且它会引发“超过最大递归深度”的RuntimeError（在sys.setrecursionlimit的递归调用之后- 在默认情况下，2.7.10中的递归调用限制为1000）。

- peroksid