Linear growth

From LifeWiki
Jump to navigation Jump to search

Linear growth is infinite growth with a rate proportional to T, where T is the number of ticks that a pattern has been run. Several common types of patterns, including guns, puffers, rakes, wickstretchers, wavestretchers, slide guns, elbow ladders and growing spaceships, demonstrate linear growth in population.

Classification

Linear growth patterns can occur in cellular automata that operate by a basic engine that repeatedly creates new objects. Both engines and objects may be loosely classified as stable (S) or moving (M), giving 22=4 types:

  • 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.
    • Puffers whose output is a single, connected, growing object, and not isolated ash, are known as wickstretchers.
  • 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.

Small infinite growth patterns in Game of Life

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). Answers and records for this question will most commonly exhibit eventual linear growth.

#N 10-cell infinite growth #O Paul Callahan #C A 10-cell infinite growth pattern found in 1997 #C No pattern with fewer cells can exhibit infinite growth x = 8, y = 6, rule = 23/3 6bob$4bob2o$4bobob$4bo3b$2bo5b$obo! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] #C [[ THUMBSIZE 2 ]]
Paul Callahan's 10-cell infinite growth pattern. No pattern with fewer cells can exhibit infinite growth
(click above to open LifeViewer)
RLE: here Plaintext: here

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 above, 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[1][2]). 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.

On October 24, 2014, Michael Simkin disovered a three-glider collision for a pattern whose ash includes a glider-producing switch engine.[3]

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:

8ob5o3b3o6b7ob5o! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] #C [[ THUMBSIZE 2 ]]
Paul Callahan's one cell thick infinite growth pattern
(click above to open LifeViewer)
RLE: here Plaintext: 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.

#N 5x5 infinite growth #O Paul Callahan #C The only pattern that fits in a 5x5 box #C that exhibits infinite growth x = 5, y = 5, rule = 23/3 3obo$o4b$3b2o$b2obo$obobo! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] #C [[ THUMBSIZE 2 ]]
The only pattern that fits in a 5 × 5 box that exhibits infinite growth
(click above to open LifeViewer)
RLE: here Plaintext: 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.[4][5] This pattern is shown below.

#N 2x12 infinite growth #O DivusIulius #C The only pattern that fits in a 2x12 #C box that exhibits infinite growth. x = 12, y = 2, rule = 23/3 o2b2ob4obo$6ob2o2bo! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] #C [[ THUMBSIZE 2 ]]
The minimally sized 2 × 12 infinite growth pattern
(click above to open LifeViewer)
RLE: here Plaintext: here

See also

References

  1. Michael Simkin (October 27, 2014). Re: Making switch-engines (discussion thread) at the ConwayLife.com forums
  2. Michael Simkin (November 5, 2014). Re: Making switch-engines (discussion thread) at the ConwayLife.com forums
  3. Michael Simkin (October 24, 2014). Re: Making switch-engines (discussion thread) at the ConwayLife.com forums
  4. "n-Cell Thick Patterns". Infinite Growth (June 5, 2009). Retrieved on June 12, 2009.
  5. DivusIulius (June 5, 2009). n-cell thick patterns & infinite growth (discussion thread) at the ConwayLife.com forums