Infinite growth
A finite pattern is said to exhibit infinite growth if it is such that 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. The first known pattern to exhibit infinite growth was the Gosper glider gun.
Small infinite growth patterns
A natural question to ask is what the smallest starting size of an infinite growth pattern can be (either in terms of number of cells or bounding box). 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 stood for more than quarter of a century until Paul Callahan found, in November 1997, two 10-cell patterns with infinite growth. The following month he found the one shown to the right, which is much neater, being a single cluster. It produces a block-laying switch engine. Nick Gotts and Paul Callahan have since shown that there is no infinite growth pattern with fewer than 10 cells, so that the question of the smallest infinite growth pattern in terms of number of cells has been answered completely.
Also of interest are some infinite growth patterns with particularly small bounding boxes. The following pattern is the smallest one cell thick pattern that exhibits infinite growth, found via computer search in October 1998 by Callahan:
Indeed, this pattern produces two block-laying switch engines at about generation 700. The following pattern (also found by Callahan) is the only pattern with infinite growth that fits inside a 5×5 bounding box. It too emits a block-laying switch engine.
Paul Callahan's pattern shows that infinite growth patterns exist in bounding boxes with area 25, but whether or not infinite growth patterns could exist in smaller boxes was not known until 2009, when exhaustive computer searches were conducted to show that there is an infinite growth pattern with bounding box 2×12 (area 24), and that this area is minimal.[1][2] This pattern is shown below.
Growth rates
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 Life:
| Growth rate f(t) | Examples |
|---|---|
| t (linear) | block-laying switch engine, Gosper glider gun |
| t2 (quadratic) | breeder 1, max |
| sqrt(t) | sqrtgun |
| t3/2 | ? |
| log(t) (logarithmic) | Caber tosser 1 |
| log(t)2 | log(t)^2 growth |
| tlog(t) | tlog(t) growth, Gotts dots |
| tlog(t)2 | ? |
It is not difficult to see that quadratic growth is the fastest possible growth rate, and many patterns that grow at such speed are now known. 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, such as the Fermat prime calculator, for which it is not known if they grow infinitely or not.
Quadratic growth
The first quadratic growth pattern constructed was the original breeder, found in 1971 by Bill Gosper. Since then, many other breeders have been found, and even some spacefillers have been constructed. It is unknown how small quadratic growth patterns can be, and a race has been taking place since the early 1990's to construct the smallest such pattern. The current record holder is 26-cell quadratic growth. Previous record holders include catacryst, metacatacryst, and the mosquitoes.
References
- ↑ "n-Cell Thick Patterns". Infinite Growth (June 5, 2009). Retrieved on June 12, 2009.
- ↑ "n-cell thick patterns & infinite growth". ConwayLife.com Forums (June 5, 2009). Retrieved on June 12, 2009.
External links
- Infinite growth at the Life Lexicon