Michael Goodyear (talk | contribs) Undid revision 625969464 by Mgoodyear (talk) OK - I see you already realised that |
David Eppstein (talk | contribs) add a reference and copyedit |
||
| Line 1: | Line 1: | ||
{{external linking|date=February 2012}} |
|||
[[Image:Seeds 140 generations.gif|frame|right|A typical chaotic "exploding" pattern in Seeds running for 140 generations.]] |
[[Image:Seeds 140 generations.gif|frame|right|A typical chaotic "exploding" pattern in Seeds running for 140 generations.]] |
||
'''Seeds''' is a [[cellular automaton]] in [[Life-like cellular automaton|the same family]] as the [[Conway's Game of Life|Game of Life]], initially investigated by [[Brian Silverman]] |
'''Seeds''' is a [[cellular automaton]] in [[Life-like cellular automaton|the same family]] as the [[Conway's Game of Life|Game of Life]], initially investigated by [[Brian Silverman]]<ref>{{citation |
||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
| work = The Virtual Computer |
|||
| publisher = [[Mathematical Association of America]]}}.</ref> and named by Mirek Wójtowicz.<ref>{{citation |
|||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
| work = [[Mirek's Cellebration]]}}.</ref> It consists of infinite two-dimensional grid of cells, each of which may be in one of two states: ''on'' or ''off''. Each cell is considered to have eight neighbors ([[Moore neighborhood]]), as in Life. In each time step, a cell turns on or is "born" if it was off or "dead" but had exactly two neighbors that were on; all other cells turn off. Thus, in the notation describing the family of cellular automata containing Life, it is described by the rule B2/S.<ref name="msz"/> |
|||
In Game of Life terminology, a pattern in which all cells that were on turn off at each step is called a ''phoenix''. All patterns in Seeds have this form. |
In Game of Life terminology, a pattern in which all cells that were on turn off at each step is called a ''phoenix''. All patterns in Seeds have this form. |
||
Even though all live cells are constantly dying, the small birth requirement of two cells means that nearly every pattern in Seeds explodes into a chaotic mess that grows to cover the entire universe. Thus, in [[Cellular automaton#Classification|Wolfram's classification of cellular automata]], it is a Class III automaton, in which nearly all patterns evolve chaotically.<ref name="msz">{{citation |
|||
| last1 = Martínez | first1 = Genaro J. |
|||
| last2 = Seck-Tuoh-Mora | first2 = Juan C. |
|||
| last3 = Zenil | first3 = Hector |
|||
| arxiv = 1304.1242 |
|||
| issue = 5–6 |
|||
| journal = Journal of Cellular Automata |
|||
| pages = 393–430 |
|||
| title = Computation and Universality: Class IV versus Class III Cellular Automata |
|||
| volume = 7 |
|||
| year = 2013}}.</ref> |
|||
However, some patterns are known that behave in a more controlled fashion, repeating the same shape either in the same position of the grid (an [[oscillator (cellular automaton)|oscillator]]) or translated some number of grid units after several steps (a [[spaceship (cellular automaton)|spaceship]]). More complex [[rake (cellular automaton)|rake]] and [[puffer train (cellular automaton)|puffer]] patterns are known which move like spaceships leaving trails of oscillators or other spaceships behind them. Most of these patterns move at a speed of 1/2 cells per time step (half of the so-called ''[[Speed of light (cellular automaton)|speed of light]]'') including three commonly seen spaceships with four on cells each, but slower-moving patterns are also known. A collection of patterns for the Seeds rule] collected by Jason Summers includes patterns found by Stephen Wright, Mirek Wójtowicz, [[Noam Elkies]], Mark Niemiec, Peter Naszvadi, and [[David Eppstein]].<ref>[http://entropymine.com/jason/life/alt/b2s.zip Jason Summers' collection of Seeds patterns]</ref> |
|||
==See also== |
==See also== |
||
* [[Brian's Brain]], a similar cellular automaton by the same author |
* [[Brian's Brain]], a similar cellular automaton by the same author |
||
==References== |
|||
{{reflist}} |
|||
==External links== |
==External links== |
||
| Line 20: | Line 43: | ||
| url = http://www.radicaleye.com/lifepage/glossary.html |
| url = http://www.radicaleye.com/lifepage/glossary.html |
||
| title = A Brief Illustrated Glossary of Terms in Conway's Game of Life}} |
| title = A Brief Illustrated Glossary of Terms in Conway's Game of Life}} |
||
*{{cite web |
|||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
| work = [http://www.maa.org/editorial/mathgames/index.html The Virtual Computer]}} |
|||
* {{cite web |
|||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
| work = [[Mirek's Cellebration]]}} |
|||
{{Conway's Game of Life}} |
{{Conway's Game of Life}} |
||
Revision as of 19:40, 17 September 2014
Seeds is a cellular automaton in the same family as the Game of Life, initially investigated by Brian Silverman[1] and named by Mirek Wójtowicz.[2] It consists of infinite two-dimensional grid of cells, each of which may be in one of two states: on or off. Each cell is considered to have eight neighbors (Moore neighborhood), as in Life. In each time step, a cell turns on or is "born" if it was off or "dead" but had exactly two neighbors that were on; all other cells turn off. Thus, in the notation describing the family of cellular automata containing Life, it is described by the rule B2/S.[3]
In Game of Life terminology, a pattern in which all cells that were on turn off at each step is called a phoenix. All patterns in Seeds have this form. Even though all live cells are constantly dying, the small birth requirement of two cells means that nearly every pattern in Seeds explodes into a chaotic mess that grows to cover the entire universe. Thus, in Wolfram's classification of cellular automata, it is a Class III automaton, in which nearly all patterns evolve chaotically.[3]
However, some patterns are known that behave in a more controlled fashion, repeating the same shape either in the same position of the grid (an oscillator) or translated some number of grid units after several steps (a spaceship). More complex rake and puffer patterns are known which move like spaceships leaving trails of oscillators or other spaceships behind them. Most of these patterns move at a speed of 1/2 cells per time step (half of the so-called speed of light) including three commonly seen spaceships with four on cells each, but slower-moving patterns are also known. A collection of patterns for the Seeds rule] collected by Jason Summers includes patterns found by Stephen Wright, Mirek Wójtowicz, Noam Elkies, Mark Niemiec, Peter Naszvadi, and David Eppstein.[4]
See also
- Brian's Brain, a similar cellular automaton by the same author
References
- ^ Brian Silverman (1996), "Changing the Rules", The Virtual Computer, Mathematical Association of America.
- ^ Mirek Wójtowicz, "Cellular Automaton Rules Lexicon — Family: Life", Mirek's Cellebration.
- ^ a b Martínez, Genaro J.; Seck-Tuoh-Mora, Juan C.; Zenil, Hector (2013), "Computation and Universality: Class IV versus Class III Cellular Automata", Journal of Cellular Automata, 7 (5–6): 393–430, arXiv:1304.1242.
- ^ Jason Summers' collection of Seeds patterns