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.

Growth geometry

Four simple types of infinite growth patterns recur in cellular automata. Three of them operate by a basic engine that repeatedly creates new objects. In simple cases this leads to linear growth of the pattern's population:

• Type SM, a.k.a. gun: a pattern that has a stationary engine and moving output.
• Type MS, a.k.a. puffer: a pattern that has a moving engine and stationary output. Puffers whose output is a single, connected, growing object, and not isolated ash, are furthermore known as wickstretchers.
• Type MM, a.k.a. rake: a pattern that has a moving engine and moving output.

The fourth type are 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.

Infinite growth patterns that have a stationary engine and stationary output are also possible. These typically involve a gun's output being periodically converted into stable output by a repeated reaction. For an example see bricklayer.

Many further types of infinite growth are possible as well, e.g. infinite glider hotel.

Small infinite growth patterns

10-cell infinite growth
RLE: here

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. Today 24 different infinite growth patterns with 10 cells are known (most of them found by Michael Simkin in 2014). 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, it produces block-laying 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:

Paul Callahan's one cell thick infinite growth pattern
Download RLE: click here

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 5×5 infinite growth pattern
RLE: here

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. This pattern is shown below.

The minimally sized 2×12 infinite growth pattern
RLE: here

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, space rake, puffer 2
t2 (quadratic)	breeder 1, max, mosquito 5, metacatacryst
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 switch engine ping-pong that consists of 23 cells. Previous record holders include catacryst, metacatacryst, mosquitoes, 26-, 25- and 24-cell quadratic growth.

External links

• Infinite growth at the Life Lexicon