A finite pattern is said to exhibit infinite growth if its population is unbounded. That is, for any number N there exists a generation n such that the population in generation n is greater than N.
Apparent infinite growth may occur in many cellular automata, and rules in which such patterns are commonplace are known as class three cellular automata. However, in many cases there is no known proof that any such pattern in fact will continue to grow indefinitely (and is not simply a particularly vigorous methuselah). Most patterns known to exhibit infinite growth start growing in a predictable way at some point in their evolution.
In Conway's Game of Life, the first known pattern to exhibit infinite growth was the Gosper glider gun. In 1971, Charles Corderman found that a switch engine could be stabilized by a pre-block in a number of different ways to produce either a block-laying switch engine or a glider-producing switch engine, giving several 11-cell patterns with infinite growth. This record for smallest infinitely-growing pattern stood for more than quarter of a century until Paul Callahan found, in November 1997, two 10-cell patterns with infinite growth (it was later determined that twenty-four 10-cell patterns exhibit infinite growth, with 17 unique pattern types). Nick Gotts and Paul Callahan have since shown that there is no infinite growth pattern with fewer than 10 cells, so the question of the smallest infinite growth pattern in terms of number of cells has been answered completely.
Infinite-growth patterns can be classified by their growth rate. In any cellular automaton, the maximum rate of growth is determined by the geometry of the space. In cellular automata set in 2D Euclidean space such as Life, the maximum growth rate is quadratic; cubic, quartic, quintic etc. growth require spaces of higher dimensionality.[note 1]
Although the simplest infinite growth patterns grow at a rate that is (asymptotically) linear, many other growth rates are possible. The following table summarizes asymptotic growth rates that have been explicitly constructed in Game of Life:
It is not difficult to see that quadratic growth is the fastest possible growth rate,[note 2] and many patterns that grow at such speed are now known. Sqrt(Log(T)) is the lowest possible growth rate for any cellular automation. There are patterns that exhibit infinite growth but whose population does not tend toward infinity – see sawtooth. By combining a sawtooth with a pattern that grows infinitely at a different rate, it is possible to construct patterns that grow (for example) logarithmically at some times and linearly at other times. There are even patterns with unknown fate, such as the Fermat prime calculator, for which it is not known if they grow infinitely or not.
- ↑ Alternatively, a faster-than-quadratic growth (including possibility of exponential growth) may be possible on a two-dimensional hyperbolic plane.
- ↑ Even if everything expanded at the speed of light, the number of cells that would be "on" would be limited by the number of cells within n generations from the starting region, which is n2.