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.
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.
- 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 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.
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|
|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.
- New pattern: LWSS breeder at Game of Life News. Posted by Dave Greene on February 28, 2009.
- These are not just breeders at Game of Life News. Posted by Adam Goucher on March 9, 2011.
- dani (March 12, 2022). Re: Cordership Discussion Thread (discussion thread) at the ConwayLife.com forums
- Luka Okanishi (March 12, 2022). Re: Cordership Discussion Thread (discussion thread) at the ConwayLife.com forums
- Rocknlol (March 23, 2022). Re: Cordership Discussion Thread (discussion thread) at the ConwayLife.com forums
- Breeder at Wikipedia