Quadratic growth

Quadratic growth is an infinite growth with a rate proportional to T², where T is the number of ticks that a pattern has been run.

A related term is breeder, which usually means an object that grows by creating an unbounded number of infinitely growing objects (demonstrating quadratic growth in population). It is usual to exclude spacefillers, because they cannot be naturally described as "objects that create other objects".

The first known breeder (and the first pattern to exhibit quadratic growth) 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 stationary (S) or moving (M), giving 2³=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). An example is Pianola breeder
• 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.
• 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. The remaining four types are general types of breeders and are more common.

An unusual type of quadratic growth 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. Spacefillers are not usually considered breeders, even though they can be loosely categorised as "MMS breeders".

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. 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, beating the previous record, a Max predecessor, and Rocknlol later found a variant with a bounding box of 23 × 13. 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.

Synthesis

On March 27, 2022, dani discovered a 6-glider synthesis for a quadratic growth pattern, eclipsing the 7-glider record set August 3, 2021 for Switch engine ping-pong.

x = 120, y = 363, rule = B3/S23 95bobo$96b2o$96bo138$117bobo$118b2o$118bo3$114b3o$116bo$115bo69$22b2o$ 23b2o$22bo71$92b3o$94bo$93bo69$2o$b2o$o! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] #C [[ THUMBSIZE 2 THEME Book ZOOM 1.5 X 70 WIDTH 800 HEIGHT 600 GPS 60 ]]

6-glider synthesis, the current minimum for a quadratic growth pattern (click above to open LifeViewer)

See also

• Quadratic growth (category)
• Pianola breeder
• Infinite growth
• Superlinear growth

External links

• Breeder at Wikipedia
• Breeder at the Life Lexicon