Rake (cellular automaton)

A rake in a cellular automaton is a puffer that, instead of leaving behind a trail of debris, emits a stream of spaceships. [ [http://www.argentum.freeserve.co.uk/lex_r.htm#rake Rake, Life lexicon] . [http://www.ericweisstein.com/encyclopedias/life/Rake.html Rake, E. Weisstein] .] In Conway's Game of Life, the discovery of rakes was one of the key components needed to form breeders, the first known patterns in Life in which the number of live cells exhibits quadratic growth. A breeder is formed by arranging several rakes so that the gliders they generate interact to form a sequence of glider guns, the gliders from which fill a growing triangle of the plane. [cite conference|author=Gardner, M.|title=The Game of Life, Part III|booktitle=Wheels, Life and Other Mathematical Amusements|year=1983|publisher=W.H. Freeman|pages=241–257] More generally, when a rake exists for a cellular automaton rule, 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. [For this reason, [http://entropymine.com/jason/life/status.html Jason Summers' life status page] describes a rake as a "versatile puffer", and collects data on the existence of rakes for various speeds and periods of puffers.] As David Bell writes, [David I. Bell, [http://members.tip.net.au/~dbell/articles/c3tech.zip Speed c/3 Technology in Conway's Life] , 1999.]

The first rake to be discovered, in the early 1970s, was the "space rake", which moves with speed "c"/2, emitting a glider every 20 steps. [ [http://www.argentum.freeserve.co.uk/lex_s.htm#spacerake Space rake, Life lexicon] . [http://www.ericweisstein.com/encyclopedias/life/SpaceRake.html Space rake, E. Weisstein] . The first published description of the space rake was in Lifeline, a newsletter published by R. Wainwright in the early 1970s, issue 3.6 ( [http://members.aol.com/life1ine/life/indx.htm index] ).] For Life, rakes are now known that move orthogonally with speeds "c"/2, "c"/3, "c"/4, "c"/5, 2"c"/5, and 17"c"/45, and diagonally with speeds "c"/4 and "c"/12, with many different periods. [ [http://entropymine.com/jason/life/status.html Jason Summers' life status page] .] Rakes are also known for some other Life-like cellular automata including HighLife, [David I. Bell, [http://members.tip.net.au/~dbell/articles/HighLife.zip HighLife - An Interesting Variant of Life] , 1994.] Day & Night, [David I. Bell, [http://members.tip.net.au/~dbell/articles/DayNight.zip Day & Night - An Interesting Variant of Life] , 1997.] and Seeds. [ [http://entropymine.com/jason/life/alt/b2s.zip Patterns for the Seeds rule] , collected by Jason Summers.]

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. [cite journal|author = Gotts, N. M.|title=Emergent phenomena in large sparse random arrays of Conway's ‘Game of Life’|journal=International Journal of Systems Science|volume=31|issue=7|pages=873–894|doi=10.1080/002077200406598|year=2000]

References