HashLife

The 6,366,548,773,467,669,985,195,496,000th (6 octillionth) generation of a Turing machine, computed in less than 30 seconds on an Intel Core Duo 2GHz CPU using HashLife in Golly.

HashLife is an algorithm created by Bill Gosper in 1984 for simulating the Game of Life. It is designed to take advantage of the considerable amount of repetitive behaviour in many large patterns of interest.

Roughly speaking, the idea of the algorithm is to store subpatterns in a hash table so that the results of their evolution don't have to be recomputed if they arise again at another place or time: 2^N+1×2^N+1 tiles are run 2^N-1 ticks into the future, and the 2^N×2^N centers are stored and re-used without recalculating them, whenever the same large hashtiles show up again. This works because information cannot travel faster than the speed of light: it is impossible for anything outside of the large tile to affect the center area in that amount of time.

This does, however, mean that complex patterns can require substantial amounts of memory. HashLife provides a means of evolving repetitive patterns millions (or even billions or trillions) of generations further than normal Life algorithms such as QuickLife can manage in a reasonable amount of time. It is not, generally, suitable for showing a continuous display of the evolution of a pattern, because it works asynchronously — at any given moment it will usually have evolved different parts of the pattern through different numbers of generations. Nonetheless, some Life simulation programs do have a HashLife mode, the most well-known example being Golly.

HashLife can be used for any outer-totalistic Life-like cellular automaton using the Moore or von Neumann neighbourhoods, but its assumptions about information not travelling at superluminal speeds make it unsuited for simulating larger Larger than Life rules without modification.

External links

• HashLife at the Life Lexicon

• HashLife at Wikipedia