Quadratic growth

From LifeWiki
Jump to navigation Jump to search

Quadratic growth is an infinite growth with a rate proportional to T2, where T is the number of ticks that a pattern has been run. A pattern that demonstrates quadratic growth in population is commonly referred to as a breeder. The first known breeder in Conway's Game of Life is breeder 1.

Classification

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

  • SSS breeder - A stationary pattern that generates copies of an SS infinite growth (e.g. a slide gun that shoots out a blockstacker-like mechanism).
  • SSM breeder - A stationary pattern that generates guns.
  • SMS breeder - A stationary pattern that generates puffers.
  • SMM breeder - A stationary pattern that generates rakes (i.e. a rake gun).
  • MSS breeder - A moving pattern that generates SS infinite growth.
  • MMS breeder - A moving pattern that generates puffers periodically. Examples include Riley's breeder, metacatacryst, Jaws and pufferfish breeder.
  • MSM breeder - A moving pattern that generates guns. Breeder 1 was a MSM breeder; so was Lucas Brown's LWSS breeder[1].
  • MMM breeder - A moving pattern that generates rakes periodically (i.e. a rake rake).

The ones in bold require the use of slide guns, so are not very frequently constructed, but some instances of breeders that can be classed as SSS and SMS do exist.[2] The remaining four types are general types of breeders and are more common.

An unusual type of breeder, which can be loosely categorised as a MMS breeder, is the spacefiller. This does not create puffers in the classical sense, but instead stretches an infinite line of wickstretchers which are dependent on each other for survival.

A ninth type are quadratic replicators, which in their basic form cannot be separated into engines and outputs. Most known natural replicators are sawtooths in their population growth rate.

Quadratic growth patterns in Game of Life

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 20-cell quadratic growth. Previous record holders are listed below.

Name Discoverer Discover date Population Bounding box
Jaws Nick Gotts February 1997 150 654 × 2881
Jaws variant Nick Gotts, Paul Callahan November 1997 130 ?
Mosquito 1 Nick Gotts September 29, 1998 103 1794 × 412
? Stephen Silver ? 97 ?
Mosquito 2 Nick Gotts October 1998 85 1644 × 315
Mosquito 3 Nick Gotts October 1998 75 2754 × 650
Mosquito 4 Stephen Silver October 1998 73 2754 × 650
Mosquito 5 Nick Gotts October 21, 1998 71 2754 × 650
Teeth Nick Gotts March 2000 65 472 × 127
Catacryst Nick Gotts April 21, 2000 58 2555 × 1772
Metacatacryst Nick Gotts December 2000 52 59739 × 14663
26-cell quadratic growth Nick Gotts March 17, 2006 26 16193 × 15089
Riley's breeder Mitchell Riley July 2006 38 135 × 41
25-cell quadratic growth Michael Simkin October 21, 2014 25 21372 × 172
24-cell quadratic growth Michael Simkin October 23, 2014 24 39786 × 143
Switch engine ping-pong Michael Simkin October 29, 2014 23 210515 × 183739
22-cell quadratic growth dani, David Raucci March 12, 2022 22 170 × 216
21-cell quadratic growth dani March 15, 2022 21 266 × 164
20-cell quadratic growth dani April 4, 2022 20 97 × 33

On March 12, 2022, dani found a pair of switch engines with perpendicular switch engines in its exhaust by searching random soups behind two pre-existing switch engines.[3] The simplest form is two switch engines and two blocks. The minimum population is 29 cells (one 8-cell switch engine, 15 cells for three gliders to create a switch engine later in the sequence, and 6 cells for two pre-blocks). Luka Okanishi found a variant with a bounding box of 26 × 18,[4] beating the previous record, a Max predecessor, and Rocknlol later found a variant with a bounding box of 23 × 13.[5] This means that quadratic growth could conceivably occur naturally, since many different pairs of two interacting switch engines have occurred from random soups.

Later in the same day, dani assembled a variant of the pattern with only 23 cells, tying the previous 23-cell switch engine ping-pong record, and David Raucci was able to adjust that to create 22-cell quadratic growth, a new record for population. Both versions set new records (by a huge margin) for bounding-box size at those populations.

On March 15, a new breeder was found which allowed for the construction of a 21-cell quadratic growth pattern. On April 4, yet another breeder was found leading to a 20-cell pattern, which is the current record holder in terms of population.

See also

References

  1. New pattern: LWSS breeder at Game of Life News. Posted by Dave Greene on February 28, 2009.
  2. These are not just breeders at Game of Life News. Posted by Adam Goucher on March 9, 2011.
  3. dani (March 12, 2022). Re: Cordership Discussion Thread (discussion thread) at the ConwayLife.com forums
  4. Luka Okanishi (March 12, 2022). Re: Cordership Discussion Thread (discussion thread) at the ConwayLife.com forums
  5. Rocknlol (March 23, 2022). Re: Cordership Discussion Thread (discussion thread) at the ConwayLife.com forums

External links