Infinite growth

From LifeWiki
Revision as of 19:59, 12 June 2009 by Nathaniel (talk | contribs) (New page: 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...)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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

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. 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:

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 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.

Paul Callahan's 5×5 infinite growth pattern
RLE: here

Nonlinear growth rates

Although the simplest infinite growth patterns grow at a rate that is (asymptotically) linear, many other growth rates are possible. It is not difficult to see that quadratic growth is the fastest possible, 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. 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

  1. "n-Cell Thick Patterns". Infinite Growth (June 5, 2009). Retrieved on June 12, 2009.
  2. "n-cell thick patterns & infinite growth". ConwayLife.com Forums (June 5, 2009). Retrieved on June 12, 2009.

External links