What technical limitations prevent the calculation of Graham's number in python?

Question

Assuming that the computer running this program has an infinite amount of memory, I'm interested in where Python will break when running the following:

For fun, I implemented hyperoperators in python as the module hyperop. One of my examples is Graham's number:

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

The condensed version of the class hyperop looks like this:

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

Essentially the library is just a recursive fold-right operation, with a special definition for the base case of n=1. Originally __call__ was beautifully golfed as:

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

However, it turns out that you can't make a list with more elements than the size of a C long. That was a fun limitation that most Python programmers probably don't encounter in their normal day-to-day and it inspired the following question.

Where, if at all, will the hyperop calculation fail due to a technical limitation of python (specifically 2.7.10)?

Janinajanine

As "the observable universe is far too small to contain an ordinary digital representation of Graham's number", I'm going to say no. Top tip: if you have to start with "this is a legitimate question" you're probably wrong! – Amphigory

Is the question about the use of yield and "infinite sequences", or something that can be pinned down more succinctly? – Espouse

Limitation of more elements than the size of a C long is only mentioned for Python 2.... – Refract

@Amphigory We're supposed to assume an infinite amount of memory, though. I'd say it's in fact a legitimate question. – Kwashiorkor

@Janinajanine What do you mean with "Python"? CPython? PyPy? Another? And which version? – Kwashiorkor

@StefanPochmann to my mind, then, it's even less legitimate. Why make one arbitrary exception, then speculate about the others? – Amphigory

@Amphigory perhaps I was too blithe with the comment that this is a "legitimate question". I merely wanted to establish that the question met the criteria for legitimacy on SO, in that it is objective (not opinion based) and there is a specific target and it is reproducible. – Janinajanine

@Amphigory Memory is an obvious reason it's impossible in reality. Whether there are any other reasons is not obvious at all, and I think it's a legitimate question. – Kwashiorkor

@PascalvKooten Good point, I think I need to pick a version of python to make this question specific. Let's establish for this question that I am using python 2.7.10, though I'd be interested in a any python 3 answers. I'll edit accordingly. – Janinajanine

You might want to edit your question title, as the answer to the title you have now is obviously "no". Since your question isn't really about Graham's number at all, but about Python's technical limitations, you might get a better response if you reframe your question to focus on specific limits imposed by Python, rather than the goal of computing Graham's number. It could be that Python does have other "hidden" limits like the one you found for list lengths, but that your particular program wouldn't hit those limits. – Inapproachable

@Inapproachable good points, and thanks for helping me get to the crux of the question. I've edited the question/title but if you'd like to clarify further please feel free to edit as well. – Janinajanine

Answer 1

Maybe original version of hyperop is robust and fails because of some esoteric cause but this exact code fails because hyperop constructor calls itself and it raises RuntimeError with "maximum recursion depth exceeded" (after sys.setrecursionlimit of recursive calls - which is 1000 in 2.7.10 by default probably).

Outrun