HashLife

HashLife is an algorithm created by Bill Gosper 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. 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 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.

External links

• HashLife at the Life Lexicon