How does the hashlife alg go on forever in Golly?

In hashlife the field is typically treated as a theoretically infinite grid, with the pattern in question centered near the origin. A quadtree is used to represent the field. Given a square of 2^(2k) cells, 2k on a side, at the kth level of the tree, the hash table stores the 2^(k-1) by 2^(k-1) square of cells in the center, 2^(k-2) generations in the future. For example, for a 4x4 square it stores the 2x2 center, 1 generation forward; and for an 8x8 square it stores the 4x4 center, 2 generations forward.

So given a 8x8 initial configuration we get a 4x4 square 1 generation forward centered w.r.t. the 8x8 square and a 2x2 square 2 generations forward (1 generation forward w.r.t the 4x4 square) centered w.r.t the 8x8 squar开发者_开发百科e. With every new generation our view of the grid reduces, in-turn we get the next state of the automata. We canot go any further after getting the inner most 2x2 square 2^(k-2) generations forward.

So how does the hashlife in Golly go on forever? Also its view of the field never seems to reduce. It seems to show the state of the whole automata after 2^(k-2) generations. More so given a starting configuration which expands with time, the view of the algorithm seems to increase. The view of the grid zooms out to show the expanding automata?

There's a good article on Dr. Dobb's which goes into detail about how HashLife works. The basic answer is that you don't merely run the algorithm on the existing nodes, you also use new shifted nodes to get the next generation.

To be clear (because your ^ symbols were missing), you are asking:

Given a square of 2^(2k) cells, 2^k on a side, at the kth level of the tree, the hash table stores the 2^(k-1)-by-2^(k-1) square of cells in the center, 2^(k-2) generations in the future. [...]

So given a 8x8 initial configuration [...] With every new generation our view of the grid reduces, in-turn we get the next state of the automata. We canot go any further after getting the inner most 2x2 square 2^k-2 generations forward.

So how does the hashlife in Golly go on forever? Also its view of the field never seems to reduce.

Instead of starting with your 8x8 pattern, imagine instead that you start with a bigger pattern that happens to contain your 8x8 pattern inside it. For example, you could start with a 16x16 pattern that has your 8x8 pattern in the center, and a 4-row margin of blank cells all around the edges. Such a pattern is easy to construct, by assembling blank 4x4 nodes with the 4x4 subnodes of your 8x8 start pattern.

Given such a 16x16 pattern, the HashLife algorithm can give you an 8x8 answer, 4 generations in the future.

You want more? Okay, start with a 32x32 pattern that contains mostly blank space, with the 8x8 pattern in the center. With this you can get a 16x16 answer that is 8 generations into the future.

What if your pattern contains moving objects that move fast enough that they go outside that 16x16 area after 8 generations? Simple -- start with a 64x64 start pattern, but instead of trying to run it for a whole 16 generations, just run it for 8 generations.

In general, all cases of arbitrarily large, possibly expanding patterns, over arbitrarily long periods of time, can be handled (and in fact are handled in Golly) by adding as much blank space as needed around the outside of the pattern.

The centered squares are only the precomputed stuff. The algorithm indeed keeps the whole universe at all times and updates all parts of it, not just the centers.