Puffer train (cellular automaton)

Puffer train (cellular automaton)

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. Puffers differ from spaceships in that spaceships do not leave debris behind. Nonetheless, puffers are considered to have periods and speeds in the same way that spaceships have. (See the article on spaceships for more information.)

The period of a puffer can be considered as the combination of "two" periods; the first is the period of the puffer itself, while the second is the apparent period of the pattern of debris produced. This is often the same as the period of the puffer, but sometimes is a factor of the period. A puffer for which the apparent period deduced from the debris is smaller than the period of the engine is a pseudoperiod puffer. Such puffers are typically produced by artificial means. A true period puffer is one in which the period of the debris matches that of the puffer.

Puffers are divided into two classes, dirty puffers and clean puffers. While there is no precise distinction, a dirty puffer is one in which there is little apparent order in the debris (although the debris will still eventually be periodic). A clean puffer, conversely, has a small amount of debris that appears much more organized. A dirty puffer can sometimes be turned into a clean puffer by adding spaceships of the same velocity as the puffer that affect what debris results.

A puffer whose debris consists entirely of spaceships is called a rake.

In Conway's Game of Life

The first known puffer, in Conway's Game of Life, was discovered by Bill Gosper; it is a dirty puffer, but eventually stabilizes to leave a pattern of debris that repeats every 140 generations. [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=247 Gosper's puffer also appears in the cover art for this book.] Since then, many puffers have been discovered for this cellular automaton, with many different speeds and periods. [ [http://entropymine.com/jason/life/status.html Jason Summers' Life status page] .] Puffers are significant for Life and related rules for three reasons: First, if they can be stabilized in such a way that they produce only gliders (that is, turned into rakes) they can be used as part of many more complex patterns such as breeders. Second, stabilizations of puffers that eliminate all of their output debris can be used to produce spaceships with arbitrarily large periods. And third, puffers can sometimes be tamed or combined to form spaceships with speeds that do not seem to be achievable in other ways; for instance, in Life, the "switch engine" is a puffer train discovered by Charles Corderman that moves diagonally at speed "c"/12, and in 1991 Dean Hickerson showed how to combine several switch engines to form a "c"/12 spaceship that he called the "Cordership". [ [http://www.math.ucdavis.edu/~dean/RLE/corder.html Corderships and puffers, D. Hickerson] . [http://www.ericweisstein.com/encyclopedias/life/Cordership.html Cordership, E. Weisstein] . [http://www.radicaleye.com/lifepage/patterns/corder.html Cordership, Lifepage] .]


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Garden of Eden (cellular automaton) — An orphan pattern in Conway s Game of Life, discovered by R. Banks in 1971.[1] …   Wikipedia

  • Oscillator (cellular automaton) — In a cellular automaton, an oscillator is a pattern that returns to its original state, in the same orientation and position, after a finite number of generations. Thus the evolution of such a pattern repeats itself indefinitely. Depending on… …   Wikipedia

  • Methuselah (cellular automaton) — The die hard Methuselah lives for 130 generations before all cells die. In cellular automata, a methuselah is a small seed pattern of initial live cells that take a large number of generations in order to stabilize. More specifically, Martin… …   Wikipedia

  • Conway's Game of Life — Conway game , which redirects to here, can also refer to games as defined by surreal numbers, which John Conway also developed …   Wikipedia

  • Day & Night — This article is about a cellular automaton rule. For other uses, see Day Night (disambiguation). Gun and antigun demonstrating the symmetric nature of Day Night. Day Night is a cellular automaton rule in the same family as Game of Life. It is… …   Wikipedia

  • Moore neighborhood — The Moore neighborhood comprises eight cells which surround center C. In cellular automata, the Moore neighborhood comprises the eight cells surrounding a central cell on a two dimensional square lattice. The neighborhood is named after Edward F …   Wikipedia

  • Mirek's Cellebration — Screenshot of Mirek s Cellebration Original author(s) Mirek Wojtowicz …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”