A rake, in the lexicon of

cellular automata A cellular automaton (pl. cellular automata, abbrev. CA) is a discrete model of computation studied in automata theory. Cellular automata are also called cellular spaces, tessellation automata, homogeneous structures, cellular structures, tessel ...

, is a type of '' puffer train'', which is an automaton that leaves behind a trail of debris. In the case of a rake, however, the debris left behind is a stream of

spaceships Spaceship may refer to: Spaceflight * Space vehicle, the combination of launch vehicle and spacecraft * Spacecraft, a craft, vehicle, vessel or machine designed for spaceflight * Starship, a spacecraft built for interstellar flight Computing ...

, which are automata that "travel" by looping through a short series of iterations and end up in a new location after each cycle returns to the original configuration. In

Conway's Game of Life The Game of Life, also known as Conway's Game of Life or simply Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970. It is a zero-player game, meaning that its evolution is determined by its initial ...

, the discovery of rakes was one of the key components needed to form the ''

breeder A breeder is a person who selectively breeds carefully selected mates, normally of the same breed, to sexually reproduce offspring with specific, consistently replicable qualities and characteristics. This might be as a farmer, agriculturalist ...

'', the first known pattern in Life in which the number of live cells exhibits

quadratic growth In mathematics, a function or sequence is said to exhibit quadratic growth when its values are proportional to the square of the function argument or sequence position. "Quadratic growth" often means more generally "quadratic growth in the limi ...

. A breeder is formed by arranging several rakes so that the '' gliders''—the smallest possible spaceships—they generate interact to form a sequence of '' glider guns'', patterns which emit gliders. The emitted gliders fill a growing triangle of the plane of the game. More generally, when a rake exists for a cellular automaton rule (a mathematical function defining the next iteration to be derived from a particular configuration of live and dead cells), one can often construct puffers which leave trails of many other kinds of objects, by colliding the streams of spaceships emitted by multiple rakes moving in parallel. As David Bell writes: Spacerake

The first rake to be discovered, in the early 1970s, was the "space rake", which moves with speed ''c''/2 (or one unit every two steps), emitting a glider every twenty steps. For Life, rakes are now known that move

orthogonal In mathematics, orthogonality (mathematics), orthogonality is the generalization of the geometric notion of ''perpendicularity''. Although many authors use the two terms ''perpendicular'' and ''orthogonal'' interchangeably, the term ''perpendic ...

ly with speeds ''c''/2, ''c''/3, ''c''/4, ''c''/5, 2''c''/5, 2''c''/7, ''c''/10 and 17''c''/45, and diagonally with speeds ''c''/4 and ''c''/12, with many different periods. Rakes are also known for some other cellular automata, including

Highlife Highlife is a Ghanaian music genre that originated along the coastal cities of present-day Ghana in the 19th century, during its Gold Coast (region), history as a colony of the British and through its trade routes in coastal areas. It encompasse ...

, Day & Night, and

Seeds In botany, a seed is a plant structure containing an embryo and stored nutrients in a protective coat called a ''testa''. More generally, the term "seed" means anything that can be sown, which may include seed and husk or tuber. Seeds are the ...

. Gotts (1980) shows that the space rake in Life can be formed by a "standard collision sequence" in which a single glider interacts with a widely separated set of 3-cell initial seeds ( ''blinkers'' and ''blocks''). As a consequence, he finds lower bounds on the probability that these patterns form in any sufficiently sparse and sufficiently large random initial condition for Life. This result leads to standard collision sequences for many other patterns such as breeders.

References

{{Conway's Game of Life Cellular automaton patterns