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 In a cellular automaton, a puffer train, or simply puffer, is a finite pattern that moves itself across the "universe", leaving debris behind. Thus a pattern consisting of only a puffer will grow arbitrarily large over time. While both puffers and ...

'', 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, 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 simply as 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 state, requiring no further ...

, 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 limit", ...

. 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 is the generalization of the geometric notion of ''perpendicularity''. By extension, orthogonality is also used to refer to the separation of specific features of a system. The term also has specialized meanings in ...

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 music genre that started in present-day Ghana in the 19th century, during its Gold Coast (British colony), history as a colony of the British Empire and through its trade routes in coastal areas. It describes multiple local fusions ...

, Day & Night, and

Seeds A seed is an embryonic plant enclosed in a protective outer covering, along with a food reserve. The formation of the seed is a part of the process of reproduction in seed plants, the spermatophytes, including the gymnosperm and angiosperm pl ...

. 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