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.
Cubic, quartic, quintic etc. growth cannot occur in 2D automata such as Life.
Contents
Growth geometry
For linear and quadratic growth patterns, S means stationary and M mobile.
Linear
Four types of linear growth patterns can occur in cellular automata that operate by a basic engine that repeatedly creates new objects. In simple cases this leads to linear growth of the pattern's population:
- Type SS, a rare type of growth with both a stationary engine and output. One example of this is bricklayer.
- Type SM, a.k.a. gun: a pattern that has a stationary engine and moving output. For example, see Simkin glider gun.
- Type MS, a.k.a. puffer: a pattern that has a moving engine and stationary output. See puffer 2 for an example.
- Type MM, a.k.a. rake: a pattern that has a moving engine and moving output. Space rake is one such pattern.
A fifth type are linear replicators, which in their basic form cannot be separated into an engine and an output. Most known natural replicators have rule 90 type growth, and are thus sawtooths in their population growth rate.
Puffers whose output is a single, connected, growing object, and not isolated ash, are known as wickstretchers
Quadratic
Quadratic growth can be split into these sections:
- MMS breeder - A moving object that generates puffers periodically. One such pattern is Riley's breeder,.
- MSM breeder - A puffer that produces guns. Gosper's original breeder was a MSM breeder; so was Lucas Brown's LWSS breeder.
- SMM breeder, a.k.a rake gun: A stationary object that produces rakes.
- MMM breeder - A moving pattern that produces rakes periodically.
Breeders that can be classed as SSS and SMS have also be constructed.^{[1]}
Quadratic replicators also exist in certain Life-like rules, for example Gnarl.
Similarly to the wickstretcher, the spacefiller is an infinite growth pattern that can be said to be MMS. This does not create puffers in the classical sense, but instead stretches an infinite line of wickstretchers.
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, bounding box or glider synthesis). 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. Today 24 different infinite growth patterns with 10 cells are known (most of them found by Michael Simkin in 2014^{[2]}^{[3]}). Nick Gotts and Paul Callahan have 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. The smallest number of gliders to synthesize infinite growth pattern is 3^{[4]}, it evolves a glider-producing switch engine, and was found by Michael Simkin in 2014.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.^{[5]}^{[6]} 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^{2} (quadratic) | breeder 1, max, mosquito 5, metacatacryst |
t^{3/2} | ? |
tlog(t)^{2} | ? |
tlog(t) | tlog(t) growth, Gotts dots |
tlog(log(t)) | Tlog(log(t)) growth |
tlog*^{(n)}(t) | Sawmill |
t (linear) | block-laying switch engine, Gosper glider gun, space rake, puffer 2 |
sqrt(t) | sqrtgun |
t^{1/3} | ? |
t^(2^(-n)) | ? |
log(t)^{2} | log(t)^2 growth |
log(t) (logarithmic) | Caber tosser 1 |
log^{(n)}(t) | ? |
log*^{(n)}(t) | Sawmill |
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 switch engine ping-pong that consists of 23 cells. Previous record holders include catacryst, metacatacryst, mosquitoes, 26-, 25- and 24-cell quadratic growth.
References
- ↑ http://pentadecathlon.com/lifeNews/2011/03/these_are_not_just_breeders.html
- ↑ "R-pentomino + R-pentomino, Glider + R-pentomino infinite growth". Infinite Growth.
- ↑ "7 and 6 cells Methuselahs infinite growth". Infinite Growth.
- ↑ "3 gliders infinite growth". Infinite Growth.
- ↑ "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 Eric Weisstein's Treasure Trove of Life
- Infinite growth at the Life Lexicon