Difference between revisions of "Cellular automaton"

From LifeWiki
Jump to navigation Jump to search
m (Grammar)
(44 intermediate revisions by 4 users not shown)
Line 1: Line 1:
{{Glossary}}
{{Glossary}}
A '''cellular automaton''' is a certain class of mathematical objects (or, more specifically, a mathematical structure) of which [[Conway's Game of Life]] is an example.
'''Cellular automata''' (CA) are a certain class of mathematical objects of which [[Conway's Game of Life]] is an example.


Informally, a cellular automaton consists of:
Informally, a cellular automaton consists of:
Line 11: Line 11:
The state of the cellular automaton evolves in discrete time, with the state of each cell at time ''t''+1 being determined by the state of its neighbourhood at time ''t'' in accordance with the transition rule.
The state of the cellular automaton evolves in discrete time, with the state of each cell at time ''t''+1 being determined by the state of its neighbourhood at time ''t'' in accordance with the transition rule.


There are some variations on the above definition. It is common to require that there be a quiescent state (i.e., a state such that if the whole universe is in that state at generation 0 then it will remain so in generation 1). In Conway's Game of Life, the "OFF" state is quiescent, but the "ON" state is not. Other variations allow spaces other than '''I'''<sup>''n''</sup>, neighbourhoods that vary over space and/or time, probabilistic or other non-deterministic transition rules, and so on.
There are some variations on the above definition. It is common to require that there be a quiescent state (i.e., a state such that if the whole universe is in that state at generation 0 then it will remain so in generation 1). In Conway's Game of Life, the "OFF" state is quiescent, but the "ON" state is not. Other variations allow spaces other than <sup>''n''</sup>, neighbourhoods that vary over space and/or time, probabilistic or other non-deterministic transition rules, and so on.


It is common for the neighbourhood of a cell to be the 3×...×3 hypercube centered on that cell, which is known as its [[Moore neighbourhood]].
One approach of the study of cellular automata focus on properties that are common to all or many (most often infinitely many) cellular automata, without regard to specific examples. Another approach studies a single or a small finite set of cellular automata for which an explicit description is given.
 
For a collection of cellular automata packaged for [[Golly]], see [https://github.com/gollygang/ruletablerepository/wiki/TheRules].


== Formal definition ==
== Formal definition ==
Let us denote the set of integers by ℤ and the length of any tuple ''x'' by |''x''|. For any tuples of integers ''x'' and ''y'' such that |''x''|=|''y''| we denote their element-wise addition by ''x''+''y''.
A '''cellular automaton''' is a tuple (ℤ<sup>''n''</sup>,''S'',''N'',''f'') such that the dimension ''n'' is at least 1, the set of states ''S'' is finite, the neighbourhood ''N'' is a tuple of elements of ℤ<sup>''n''</sup> and ''f'':''S''<sup>|''N''|</sup>→''S'' is the transition function.
A '''configuration''' of the cellular automaton (ℤ<sup>''n''</sup>,''S'',''N'',''f'') is any function ℤ<sup>''n''</sup>→''S''.
The '''global transition function''' ''F'' of the cellular automaton (ℤ<sup>''n''</sup>,''S'',''N'',''f'') is a function from configurations to configurations ''F'':(ℤ<sup>''n''</sup>→''S'')→(ℤ<sup>''n''</sup>→''S'') such that for any configuration ''c'' and element ''a''∈ℤ<sup>''n''</sup> we have ''F''(''c'')(''a'')=''f''(''a''+''N'').
Let ''c'' be a configuration. When the cellular automata is clear from the context, then by ''c''<sup>''n''</sup> where ''n'' is a non-negative integer we denote the configuration ''F''<sup>''n''</sup>(''c'') where ''F'' is the corresponding global transition function.
Let ''c'' and ''c''′ be configurations, then we say that ''c''′ is a '''translation''' of ''c'' if there exist an ''a''∈ℤ<sup>''n''</sup> such that for any ''x''∈ℤ<sup>''n''</sup> it holds that ''c''′(''a''+''x'')=''c''(''x''). We say that the translation is proper if the condition holds for some ''n''-tuple whose elements are not all 0.
For any configuration ''c'', if there exists a ''n''≥1 such that ''c''<sup>''n''</sup> = ''c'' we call ''c'' an '''oscillator'''. If ''c'' is an oscillator and ''n'' is the least positive integer such that ''c''<sup>''n''</sup> = ''c'' then we call ''n'' the '''period''' of ''c''. If ''c'' is an oscillator with period 1 then we call ''c'' a '''still life'''. If ''c'' is an oscillator and is not a still life we call ''c'' a '''proper oscillator'''.
A '''glider''' is a configuration ''c'' such that ''c''<sup>''n''</sup> is a proper translation of ''c'' for some ''n''>0.
Our definition of cellular automaton is a simple derivative of the one given in [[#Codd_1968|Codd (1968)]]. The only difference in scope is that Codd only allows grids of dimension 2 and requires the presence of a quiescent state, that is, a state ''v''<sub>0</sub> such that ''f''(''v''<sub>0</sub>,...,''v''<sub>0</sub>)=''v''<sub>0</sub>. Moreover, Codd only allows configurations in which finitely many cells are non-quiescent, while our definition of configuration allows any assignment of states to cells.
== Common dimensions and neighborhoods ==
In the approach that studies a small set of automata which are explicitly described the most common space is by far ℤ<sup>2</sup>. This space can be easily represented in a computer screen or in print, is easy to manipulate, and geometric intuition is applicable. Some explicitly described cellular automata on ℤ<sup>1</sup> and ℤ<sup>3</sup> have also been studied. A disadvantage of ℤ<sup>1</sup> is that information transfer requires many path crossings. In ℤ<sup>3</sup> path crossings can be entirely avoided, but is harder to represent than ℤ<sup>1</sup> and ℤ<sup>2</sup>. The most common neighbourhoods of CA in ℤ<sup>2</sup> are shown below.
{| style="width: 100%; left-margin: auto; right-margin: auto; border-collapse: collapse;" cellpadding="0"
|- style="vertical-align: top;"
|
{| style="margin: 0 auto; border-spacing: 1em 0;" cellpadding="0"
|- style="vertical-align: top;"
| [[File:Vonneumannneighbourhood_1cell.png|frame|none|The [[von Neumann neighbourhood]].]]
| [[File:Hexagonal neighbourhood (radius 1).png|frame|none|The [[hexagonal neighbourhood]].]]
| [[File:Mooreneighbourhood 1cell.png|frame|none|The [[Moore neighbourhood]].]]
|}
| [[File:Representation_of_the_hexagonal_neighbourhood_on_the_square_tessellation.png|frame|center|Representation of the hexagonal neighbourhood on the square tessellation.]]
|}
For each dimension ''n''≥1 and radius ''r''≥0 we define the corresponding neighbourhoods:
*The '''generalized von Neumann neighbourhood''' is the set {''x''∈ℤ<sup>''n''</sup>|(<small>MAX</small><sub>0≤''i''≤''n''-1</sub>|''x''<sub>''i''</sub>|)<''r''}.
*The '''generalized Moore neighbourhood''' is the set {''x''∈ℤ<sup>''n''</sup>|(Σ<sub>0≤''i''≤''n''-1</sub>|''x''<sub>''i''</sub>|)<''r''}.
*The '''Euclidean neighbourhood''' is the set {''x''∈ℤ<sup>''n''</sup>|(√Σ<sub>0≤''i''≤''n''-1</sub>''x''<sub>''i''</sub><sup>2</sup>)<''r''}.
See ''[[Gallery of neighbourhoods]]'' illustrations of some instances in ℤ<sup>2</sup>.
Other tesselations, such as the [[Triangular neighbourhood|triangular]]<ref>http://www.conwaylife.com/forums/viewtopic.php?f=7&t=2036&p=43653&hilit=Triangular#p43653</ref> and [[Cairo pentagonal neighbourhood|Cairo pentagonal]] tesselations, have been investigated; the former can be simulated on the square grid using 4 states that divide each cell into two right triangles.<ref>https://github.com/gollygang/ruletablerepository/wiki/TheRules</ref>
== Generalizations and topological characterization ==
Our definition is enough to describe most of the cellular automata in which explicitly described configurations are studied. In particular it handles as expected the elementary cellular automata, CA on the Euclidean square tessellation (including all life-like CA and all non-totalistic life-like CA) and the Euclidean hexagonal tessellation. Furthermore, CA on the Euclidean triangular tessellation can be handled when proper care is taken. However, there exist objects which are cellular automata according to our informal description, but can not be defined as such in our formal definition. An example is cellular automata in hyperbolic tessellations ([[#Margenstern_2013|Margenstern, 2013]]). A very general definition of cellular automata is given in [[#Moriceau_2011|Moriceau (2011)]] and a further generalization is given in [[#Wacker_2016|Wacker (2016)]]. Interestingly, Wacker's definition uses amenable groups. Both amenable groups and cellular automata were introduced by the same man: John von Neumann.
A remarkable result, the '''Curtis-Hedlund-Lyndon-Richardson (CHLR) theorem''', relates cellular automata theory with topology and dynamical system theory. An informal statement is given as follows: Let the set of states be given the discrete topology and the configuration space be given the Tikhonov topology; then the global transition functions of the cellular automata over the configuration space are exactly those functions which are continuous and commute with the translations of the cellular space. In particular, the CHLR theorem holds for our definition of CA. Informally we state that the CHLR theorem holds for definitions of CA where the set of states is required to be finite, but if the set of states is allowed to be infinite, the set of allowable neighborhoods must be expanded or a further constraint must be imposed on continuous functions so that an analogous result holds ([[#Ceccherini-Silberstein_2010|Ceccherini-Silberstein 2010]]; [[#Sobottka_2015|Sobottka 2015]]). Generally when a novel definition of cellular automaton is presented a corresponding version of the CHLR theorem is proved in the same treatise.
The CHLR theorem was demonstrated independently by [[#Hedlund_1969|Hedlund (1969)]] (in this paper credit is given to Curtis and Lyndon in addition to the author) and [[#Richardson_1972|Richardson (1972)]]. Neither of these papers use the term “cellular automaton”. Nonetheless the systems they study are, respectively, 2-dimensional deterministic cellular automata and ''n''-dimensional non-deterministic cellular automata.
=== Block cellular automata ===
In the above definitions of cellular automata, the transition function takes the state of a set of possibly many cells and gives the next state for a single cell. '''Block cellular automata (BCA)''' use an alternative approach. In a BCA each configuration is augmented with a partition of the sets of cells into subsets of of finite size. Call this partition ''p''(''c'') for any configuration ''c''. The local transition function takes the state of all the cells in an element of ''p''(''c'') and generates a new state for all those cells, instead of only for a single cell. The partitioning of a configuration ''c'' needs not be the same as ''c''<sub>1</sub>. If that was the case, the state of one cell could never affect the state of any cell outside its partition. However, the partitioning must be independent of the states of cells. In the context of BCA the partitioning scheme is called the neighborhood.
The motivation to study block cellular is the ease with which reversible global transition functions can be generated. The local transition rule of a BCA is injective if and only if it is bijective. Any bijective local transition function generates a bijective global transition function. All block cellular automata can be transformed into equivalent classical cellular automata at the expense of adding more states or expanding the neighborhood.
The most commonly studied partition is the Margolous neighborhood. This partitioning scheme is defined for ℤ<sup>2</sup>. The partition is a grid of blocks of cells of size 2×2. The blocks are shifted one cell vertically and horizontally after each time step; therefore the partition repeats with period 2. In other words, given a configuration ''c'', the cell space is partitioned along the green-blue lines to compute ''c''<sub>''n''+1</sub> from ''c''<sub>''n''</sub> for even ''n'' and along the red lines to compute ''c''<sub>''n''+1</sub> from ''c''<sub>''n''</sub> for odd ''n''.
{| style="margin-left: auto; margin-right: auto; border-spacing: 2em 0;" cellpadding="0"
|- style="vertical-align: top;"
| [[File:Margolous_neighbourhood.png|frame|none|The Margolous neighbourhood.]]
| [[File:Effective_Margolous_neighbourhood_of_a_single_cell.png|frame|none|The neighborhood of a single cell effectively switches as shown every time step.]]
|}
== Self-replicating configurations ==
Informally, a configuration that creates a copy of itself after some number of generations is called a [[replicator]].
John von Neumann investigated the possibility of building a self-replicating machine. He originally considered a mechanical approach, but decided that this was too hard to control. With the help of Stanislaw Ulam, he designed a new mathematical abstraction, the cellular automaton, in order to create a [[replicator]]. His CA was made in the late 1940s and is complex. It operates on the [[Von Neumann neighbourhood]] (a cell and its four orthogonally connected neighbours), and has 29 states. It is described in [[#von_Neumann_1966|von Neumann, Burks (1966)]].
Subsequent to the von Neumann's cellular automaton new cellular automata have been produced capable of self-replication and universal computation with fewer states and using the same (von Neumann) neighborhood. Results include [[#Codd_1968|Codd (1968)]] with 8 states, [[#Banks_1971|Banks (1971)]] with 4 states and [[#Serizawa_1987|Serizawa (1987)]] with 3 states. As of 2017, Serizawa's CA appears to be the simplest (in terms of neighborhood size×number of states) cellular automaton known to have a non-trivial replicator.
[[#Langton_1984|Langton (1984)]] constructed a cellular automaton and a replicator. His cellular automaton is a simplification of Codd's. However, Langton's CA was not intended to support universal computation. The simplicity of the configuration is possible because of a novel method of self-replication. The replicator consists of a loop with circulating cell states that encode instructions to construct a new arm, then turn 90° and repeat until a new loop is formed. The new loop is then filled with the same circulating information and the connection between it and the loop that generated it is severed. The parent loop continues to build copies until no more space is available, then it becomes a still life.
[[#Nehaniv_2002|Nehaniv (2002)]] presented a method that allows the transformation of conventional (synchronous) cellular automata to an equivalent asynchronous cellular automata (a case not covered by our definition above). In the same paper, a self-reproducing configuration is presented which is based on the described procedure applied to Langton's CA.
Conway's Game of Life is known to be universal, with 2 states and the Moore neighbourhood. Conway did not design Life for this purpose, unlike von Neumann's, Codd's, Banks' and Serizawa's rules, so it is purely coincidental that Life supports replicators. The [[Spartan universal computer-constructor]] could replicate, given a sufficient program tape. Between 2010 and 2017 much more efficient construction mechanisms have been developed that can be used for self-replication, but to date only a limited one-dimensional example has actually been completed (the [[linear propagator]]).


Let us denote the set of integers by '''I''' and the length of any tuple ''x'' by |''x''|. For any tuples of integers ''x'' and ''y'' such that |''x''|=|''y''| we denote their element-wise addition by ''x''+''y''.
=== Formal definition ===
There are several possible non-equivalent definitions of self-replicators. [[#Moore_1962|Moore (1962)]] proposed a simple definition which does not attempt to exclude trivial cases (although Moore wrote “self-reproduction”, we assume that it synonymous with “self-replication”). However, his definitions of self-replicator is limited to the same cellular automata and configurations allowed by the definition of [[#Codd_1968|Codd (1968)]]. Our definition is a slight generalization of Moore's definition to cover all the configurations allowed by our definition.


A '''cellular automaton''' is a tuple ('''I'''<sup>''n''</sup>,''S'',''N'',''f'') such that the dimension ''n'' is at least 1, the set of states ''S'' is finite, the neighbourhood ''N'' is a tuple of elements of '''I'''<sup>''n''</sup> and ''f'':''S''<sup>|''N''|</sup>→''S'' is the transition function.
Not all of the self-replicators mentioned above meet our formal definition. Langton's self-replicating loop and the [[HighLife#The replicator|classical HighLife replicator]] meet our definition. Typically the configurations in which each copy of the initial configuration only generates one copy but does not returns to the initial state after finishing do not meet our definition.


A '''configuration''' of the cellular automaton ('''I'''<sup>''n''</sup>,''S'',''N'',''f'') is any function '''I'''<sup>''n''</sup>''S''.
'''Definition:''' Let (<sup>''n''</sup>,''S'',''N'',''f'') be a cellular automaton. Let ''c'' be a configuration such that for some ''s''∈''S'' the set ''X''={''a''∈ℤ<sup>''n''</sup>|''c''(''a'')≠''s''} is finite. We say that ''c'' is a '''finite configuration''', ''s'' is a '''background state''' of ''c'' and ''X'' is a '''support''' of ''c''.


The '''global transition function''' ''F'' of the cellular automaton ('''I'''<sup>''n''</sup>,''S'',''N'',''f'') is a function ''F'':'''I'''<sup>''n''</sup>→'''I'''<sup>''n''</sup> such that for any configuration ''c'' and element ''a''∈'''I'''<sup>''n''</sup> we have ''F''(''c'')(''a'')=''f''(''a''+''N'').
'''Theorem:''' Let ''c'' be a finite configuration, then there is a unique background state and support of ''c''.


Let ''c'' and ''c'<nowiki/>'' be configurations, then we say that ''c'<nowiki/>'' is a '''translation''' of ''c'' if there exist an ''a'''''I'''<sup>''n''</sup> such that for any ''x'''''I'''<sup>''n''</sup> it holds that ''c'<nowiki/>''(''a''+''x'')=''c''(''x''). We say that the translation is proper if the condition holds for some ''n''-tuple whose elements are not all 0.
: Let ''v'' and ''v''′ be background states of ''c''. Let ''X'' be the set of all cells ''a'' such that ''c''(''a'')≠''v'' and respectively for ''X''′ and ''v''′. The set ℤ<sup>''n''</sup>\(''X''∪''X''′) is non-empty because ℤ<sup>''n''</sup> is infinite and ''X''''X''′ is finite. Let ''x''∈ℤ<sup>''n''</sup>\(''X''''X''′). By the properties of set union and complement we have ''x''∈ℤ<sup>''n''</sup>\''X'' and ''x''∈ℤ<sup>''n''</sup>\''X''′; by definition of ''X'' and ''X''′ we have ''x''=''v'' and ''x''=''v''′; therefore ''v''=''v''′. Again from the definition of ''X'' and ''X''′ it follows that ''X''=''X''.


Let ''c'' be a configuration. When the cellular automata is clear from the context, then by ''c''<sup>''n''</sup> where ''n'' is a non-negative integer we denote the configuration ''F''<sup>''n''</sup>(''c'') where ''F'' is the corresponding global transition function.
'''Definition:''' Let ''c'' be a finite configuration. We write <small>bg</small>(''c'') for the background state of ''c'' and we write <small>su</small>(''c'') for the support of ''c''.
 
'''Definition:''' Let ''c'' and ''c''′ be finite configurations such that <small>bg</small>(''c'')=<small>bg</small>(''c''′). If <small>su</small>(''c'')∩<small>su</small>(''c''′)=∅ we say that ''c'' is '''disjoint''' from ''c''′. If <small>su</small>(''c'')⊂<small>su</small>(''c'') and for all ''a''∈<small>su</small>(''c'') we have ''c''(''a'')=''c''′(''a'') then we say that ''c''′ '''contains''' ''c''.


For any configuration ''c'', if there exists a ''n''≥1 such that ''c''<sup>''n''</sup> = ''c'' we call ''c'' an '''oscillator'''. If ''c'' is an oscillator and ''n'' is the least positive integer such that ''c''<sup>''n''</sup> = ''c'' then we call ''n'' the '''period''' of ''c''. If ''c'' is an oscillator with period 1 then we call ''c'' a '''still life'''. If ''c'' is an oscillator and is not a still life we call ''c'' a '''proper oscillator'''.
'''Definition:''' Let ''c'' and ''c''′ be configurations. We say that ''c'''''contains at least''' ''n'' copies if ''c'' if there exist a set ''X'' of pairwise disjoint translations of ''c'' and for each ''x''''X'', ''c'' contains ''x''.


A '''glider''' is a configuration ''c'' such that ''c''<sup>''n''</sup> is a proper translation of ''c'' for some ''n''>1.
'''Definition:''' A configuration ''c'' is called a ''self-replicator'' if for any ''n''≥1 there exist a ''t''≥0 such that ''c''<sub>''t''</sub> contains at least ''n'' disjoint copies of ''c''.


== Self-replication in cellular automata ==
'''Definition:''' Let ''c'' and ''c<nowiki/>'' be a configuration. Let ''n''≥0 be an integer. If ''c''′ contains at least ''n'' copies of ''c'' and for any integer ''k''>''n'' it is not the case that ''c''′ contains at least ''k'' copies of ''c'' then we say that ''c''′ '''contains exactly'''  ''n'' copies of ''c''.
John von Neumann investigated the possibility of building a self-replicating machine. He originally considered a mechanical approach, but decided that this was too hard to control. With the help of Stanislaw Ulam, he designed a new mathematical abstraction, the cellular automaton, in order to create a [[replicator]]. His rule was made in the late 1940s and was very complex. It operates on the [[Von Neumann neighbourhood]] (a cell and its four orthogonally connected neighbours), and has a grand total of 29 states. Edgar F. Codd subsequently designed a rule with just 8 states capable of self-replication, and Edwin Banks reduced this to just four states. Life is known to be universal, with just two states and the Moore neighbourhood. Conway did not design Life for this purpose, unlike von Neumann's, Codd's and Banks' rules, so it is purely coincidential that Life supports replicators. The [[Spartan universal computer-constructor]] could replicate, given a sufficient program tape.


== Life-like cellular automata ==
== Life-like cellular automata ==
:''Also see: [[Totalistic Life-like cellular automaton]]''
A cellular automaton is said to be '''Life-like''' if it meets the following four criteria:
A cellular automaton is said to be '''Life-like''' if it meets the following four criteria:


* It has two dimensions (i.e., n = 2).
* It has two dimensions (i.e., ''n''=2).
* It has two states, usually called OFF and ON (i.e., |S| = 2).
* It has two states, usually called OFF and ON (i.e., |''S''|=2).
* The neighbourhood used is the Moore neighbourhood; it consists of the eight (orthogonally and diagonally) adjacent cells to the one under consideration and (possibly) the cell itself.
* The neighbourhood used is the Moore neighbourhood.
* The new state of a cell in the next [[generation]] can be expressed as a function of the number of cells in its neighbourhood that are in the ON state and the cell's own state; that is, the rule is ''outer totalistic'' (or ''semitotalistic'').
* The new state of a cell in the next [[generation]] can be expressed as a function of the number of cells in its neighbourhood that are in the ON state and the cell's own state; that is, the rule is ''outer totalistic'' (also called ''semitotalistic'').


This class of cellular automata is named for [[Conway's Game of Life]], the most famous cellular automaton, which Life-like cellular automata mimic. Many different terms are used to describe this class of cellular automata; it is also common to refer to it as the "Life family" or to simply use phrases like "similar to Life".  
This class of cellular automata is named for [[Conway's Game of Life]], the most famous cellular automaton, which Life-like cellular automata mimic. Many different terms are used to describe this class of cellular automata; it is also common to refer to it as the "Life family" or to simply use phrases like "similar to Life".


=== Rules ===
=== Rules ===
A common notation used to describe these automata is referred to as "S/B", which is known as its '''rule''' (or '''rulestring'''). S (for survival) is a list of all the numbers of ON cells that cause an ON cell to remain ON. B (for birth) is a list of all the numbers of ON cells that cause an OFF cell to turn on. If 0 is in the list, then blank regions of the universe will turn on in one generation. S/B is often referred to as the rule or rulestring of the given cellular automata.
Rules are typically expressed as [[rulestring]]s in B/S notation, with two lists of numbers giving the live neighbour counts that cause a dead cell to be born or a live cell to survive, respectively; Conway's Game of Life has the rulestring B3/S23.
 
As an example, the [[seeds]] rulestring is /2. All OFF cells that have exactly two adjacent ON cells will turn on in the next generation, while every ON cell dies in every generation, since the survival list is empty. The rulestring of Conway's Game of Life is 23/3.
 
Other notations are sometimes used to describe the rules of the given Life-like cellular automaton. The most common other format is "B{number list}/S{number list}", where the number lists are the numbers of neighbours that cause a dead cell to be born and cause an alive cell to stay alive, respectively. In this format, Conway's Game of Life would have the rulestring B3/S23.


There are 262144 (= 2<sup>18</sup>) distinct Life-like rules. Each rule has a complementary rule which behaves identically under on-off reversal; namely the rule in which birth occurs on all N except those for which 8-N is a survival condition in the original rule, and survival occurs on all N except those for which 8-N is a birth condition in the original rule. For example, the rule complementary to Conway's Life is 01234678/0123478. This however does not quite halve the number of effectively distinct rules, as there are 512 (= 2<sup>9</sup>) rules which are unaffected by on-off reversal.
There are 262144 (= 2<sup>18</sup>) distinct Life-like rules. Each rule has a complementary rule which behaves identically under [[black/white reversal|on-off reversal]]; namely the rule in which birth occurs on all N except those for which 8-N is a survival condition in the original rule, and survival occurs on all N except those for which 8-N is a birth condition in the original rule. For example, the rule complementary to Conway's Life is 01234678/0123478. This however does not quite halve the number of effectively distinct rules, as there are 512 (= 2<sup>9</sup>) [[self-complementary]] rules which are unaffected by on-off reversal.


Some straightforward inferences on the behavior of different kinds of rules can be made:
Some straightforward inferences on the behavior of different kinds of rules can be made:
Line 63: Line 140:
* This leaves 16384 rules in which the lowest birth condition is 3 neighboring ON cells, as well as 65536 rules in which the lowest birth condition is 0 neighboring cells, and 8 neighbors is not a survival condition. All chaotic rules must fall in either of these two areas of the rulespace. Most well-studied examples fall in the first one, since for long no commonly available software existed that could simulate the evolution of rules containing B0.
* This leaves 16384 rules in which the lowest birth condition is 3 neighboring ON cells, as well as 65536 rules in which the lowest birth condition is 0 neighboring cells, and 8 neighbors is not a survival condition. All chaotic rules must fall in either of these two areas of the rulespace. Most well-studied examples fall in the first one, since for long no commonly available software existed that could simulate the evolution of rules containing B0.


=== Non-totalistic rules ===
=== Generalizations ===
:''Main article: [[Non-totalistic Life-like cellular automaton]]''
:''Main articles: [[Non-totalistic Life-like cellular automaton]], [[Non-isotropic Life-like cellular automaton]], [[Generations]], [[Larger than Life]]''
Various generalizations of Life-like cellular automata are possible. In non-totalistic rules, the transition function considers not just the number of cells in a given cell's neighborhood but also their alignment; for example, a cell might be born if bordered by three live cells in a row, but not by three live cells in other configurations. Non-totalistic rules are described using [[Hensel notation]], an extension of B/S notation additionally describing allowed or forbidden configurations.


=== Well-known Life-like cellular automata ===
Various generalizations of Life-like cellular automata are possible. In [[Non-totalistic Life-like cellular automaton|non-totalistic]] (but isotropic) rules, the transition function considers not just the number of cells in a given cell's neighborhood but also their relative alignment; for example, a cell might be born if bordered by three live cells in a row, but not by three live cells in other configurations. Non-totalistic rules are described using [[Hensel notation]], an extension of B/S notation additionally describing allowed or forbidden configurations.
 
In [[Non-isotropic Life-like cellular automaton|non-isotropic]] rules, the transition function additionally considers the absolute placement of a given cell's neighborhood; for example, a cell might be born if it is bordered by two live neighbors on the north and northeast, but not if it is bordered by two live neighbors on the south and southwest. Non-isotropic rules are described using [[MAP]] strings, a notation unrelated to B/S notation.
 
In [[Generations]] rules, additional states are introduced, and cells that do not survive into the next generation instead progress through the subsequent states before dying. Cells in these additional states do not count as live neighbors for the purpose of evolution.
 
In [[Larger than Life]] rules, the size of a cell's neighborhood is extended to include cells with a distance greater than one. As in [[Generations]] rules, non-surviving cells may decay through additional states instead of dying outright.
 
=== Well-known life-like cellular automata ===
:''Main article: [[List of Life-like cellular automata]]''
:''Main article: [[List of Life-like cellular automata]]''


The following table lists rules that are particularly well-known or well-studied.  
The following table lists life-like cellular automata that are particularly well-known or well-studied.


{| class="wikitable"
{| class="wikitable"
Line 85: Line 169:
| B3/S012345678 || [[Life without death]] || An expanding rule that produces complex flakes. It also has important [[ladder]] patterns.
| B3/S012345678 || [[Life without death]] || An expanding rule that produces complex flakes. It also has important [[ladder]] patterns.
|-
|-
| B3/S12 || [[Flock]] || A rule which decays into small still lifes and oscillators
| B3/S12 || [[Flock]] || A rule which rapidly decays into small still lifes and oscillators.
|-
|-
| B3/S1234 || [[Mazectric]] || An expanding rule that crystalizes to form maze-like designs that tend to be straighter (ie. have longer "halls") than the standard maze rule.
| B3/S1234 || [[Mazectric]] || An expanding rule that crystalizes to form maze-like designs that tend to be straighter (ie. have longer "halls") than the standard maze rule.
Line 100: Line 184:
|-
|-
| B3678/34678 || [[Day & Night]] || A stable rule that is symmetric under on-off reversal. Many patterns exhibiting highly complex behavior have been found for it.
| B3678/34678 || [[Day & Night]] || A stable rule that is symmetric under on-off reversal. Many patterns exhibiting highly complex behavior have been found for it.
|-
| B37/S23 || [[DryLife]] || An explosive rule that resembles the regular Game of Life, but the weighted spaceships do not function, and there exists [[9c/28 orthogonal]] technology.
|-
| B38/S23 || [[Pedestrian Life]] || A chaotic rule that strongly resembles regular Life, with many exciting natural technologies.
|}
|}
== References ==
<references />
*<span id="Banks_1971">Banks, E. R. (1971) [http://www.bottomlayer.com/bottom/banks/banks_thesis_1971.pdf ''Information processing and transmission in cellular automata''].</span>
*<span id="Ceccherini-Silberstein_2010">Ceccherini-Silberstein, T.; Coornaert, M. (2010) ''Cellular Automata and Groups''. DOI: 10.1007/978-3-642-14034-1. ISBN: 978-3-642-14033-4, 978-3-642-14034-1.</span>
*<span id="Codd_1968">Codd, E. F. (1968) ''Cellular Automata''. No ISBN. WorldCat OCLC number: [https://www.worldcat.org/title/cellular-automata/oclc/637978742 637978742].</span>
*<span id="Hedlund_1969">Hedlund, G. A. (1969) ''Endomorphisms and Automorphisms of the Shift Dynamical System''. DOI: 10.1007/BF01691062.</span>
*<span id="Langton_1984">Langton, C. G. (1984) ''Self-reproduction in cellular automata''. DOI: 10.1016/0167-2789(84)90256-2.</span>
*<span id="Margenstern_2013">Margenstern, M. (2013) ''Small Universal Cellular Automata in Hyperbolic Spaces: A Collection of Jewels''.</span>
*<span id="Moore_1962">Moore, E. F. (1962) ''Machine models of self-reproduction'' in ''Mathematical Problems in the Biological Sciences''. DOI: 10.1090/psapm/014/9961.</span>
*<span id="Moriceau_2011">Moriceau, S. (2011) ''Cellular automata on a ''G''-set''. arXiv: [https://arxiv.org/abs/1105.5335 1105.5335 [math.DS<nowiki>]</nowiki>].</span>
*<span id="Nehaniv_2002">Nehaniv, C. E. (2002) [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.7.2073&rep=rep1&type=pdf ''Self-Reproduction in Asynchronous Cellular Automata''] in ''Proceedings 2002 NASA/DoD Conference on Evolvable Hardware''. DOI: 10.1109/eh.2002.1029854.</span>
*<span id="Richardson_1972">Richardson, D. (1972) ''Tessellation with Local Transformations''. DOI: 10.1016/S0022-0000(72)80009-6.</span>
*<span id="Serizawa_1987">Serizawa, T. (1987) ''Three-State Neighbor Cellular Automata Capable of Constructing Self-Reproducing Machines''. DOI: 10.1002/scj.4690180404.</span>
*<span id="Sobottka_2015">Sobottka, M.; Gonçalves, D. (2015) ''A note on the definition of siding block codes and the Curtis-Hedlund-Lyndon Theorem''. arXiv: [https://arxiv.org/abs/1507.02180 1507.02180 [math.DS<nowiki>]</nowiki>].</span>
*<span id="von_Neumann_1966">von Neumann, J.; Burks, A. W. (1966) [https://archive.org/download/theoryofselfrepr00vonn_0/theoryofselfrepr00vonn_0.pdf ''Theory of Self-Reproducing Automata'']. No ISBN. WorldCat OCLC number: [https://www.worldcat.org/title/theory-of-self-reproducing-automata/oclc/7298386 7298386].</span>
*<span id="Wacker_2016">Wacker, S. (2016) ''Cellular Automata on Group Sets and the Uniform Curtis-Hedlund-Lyndon Theorem''. DOI: 10.1007/978-3-319-39300-1_15. In ''Cellular Automata and Discrete Complex Systems. AUTOMATA 2016.''</span>


== External links ==
== External links ==
{{LinkMirek|ca_rules.html|title=Cellular automata rules lexicon}}
{{LinkMirek|ca_rules.html|title=Cellular automata rules lexicon}}
{{LinkLexicon|lex_c.htm#cellularautomaton}}
{{LinkLexicon|lex_c.htm#cellularautomaton}}
{{LinkMathworld|CellularAutomaton.html|pagename=Cellular Automaton}}
{{LinkMathworld|TotalisticCellularAutomaton.html|pagename=Totalistic Cellular Automaton}}
*[https://github.com/gollygang/ruletablerepository/wiki/TheRules Rule Table Repository]
*[https://github.com/gollygang/ruletablerepository/wiki/TheRules Rule Table Repository]

Revision as of 14:39, 25 February 2018

Cellular automata (CA) are a certain class of mathematical objects of which Conway's Game of Life is an example.

Informally, a cellular automaton consists of:

  • A space of cells.
  • A set of allowed states for each cell. An assignment of an state to every cell is called a “configuration” or “pattern” (the first term is more common in mathematical discussion and the later in informal discussions).
  • A neighbourhood which defines which cells are considered to pass information to a given cell.
  • A transition rule which specifies how given a cell and the states of its neighbours, a new state is produced.

The state of the cellular automaton evolves in discrete time, with the state of each cell at time t+1 being determined by the state of its neighbourhood at time t in accordance with the transition rule.

There are some variations on the above definition. It is common to require that there be a quiescent state (i.e., a state such that if the whole universe is in that state at generation 0 then it will remain so in generation 1). In Conway's Game of Life, the "OFF" state is quiescent, but the "ON" state is not. Other variations allow spaces other than ℤn, neighbourhoods that vary over space and/or time, probabilistic or other non-deterministic transition rules, and so on.

One approach of the study of cellular automata focus on properties that are common to all or many (most often infinitely many) cellular automata, without regard to specific examples. Another approach studies a single or a small finite set of cellular automata for which an explicit description is given.

For a collection of cellular automata packaged for Golly, see [1].

Formal definition

Let us denote the set of integers by ℤ and the length of any tuple x by |x|. For any tuples of integers x and y such that |x|=|y| we denote their element-wise addition by x+y.

A cellular automaton is a tuple (ℤn,S,N,f) such that the dimension n is at least 1, the set of states S is finite, the neighbourhood N is a tuple of elements of ℤn and f:S|N|S is the transition function.

A configuration of the cellular automaton (ℤn,S,N,f) is any function ℤnS.

The global transition function F of the cellular automaton (ℤn,S,N,f) is a function from configurations to configurations F:(ℤnS)→(ℤnS) such that for any configuration c and element a∈ℤn we have F(c)(a)=f(a+N).

Let c be a configuration. When the cellular automata is clear from the context, then by cn where n is a non-negative integer we denote the configuration Fn(c) where F is the corresponding global transition function.

Let c and c′ be configurations, then we say that c′ is a translation of c if there exist an a∈ℤn such that for any x∈ℤn it holds that c′(a+x)=c(x). We say that the translation is proper if the condition holds for some n-tuple whose elements are not all 0.

For any configuration c, if there exists a n≥1 such that cn = c we call c an oscillator. If c is an oscillator and n is the least positive integer such that cn = c then we call n the period of c. If c is an oscillator with period 1 then we call c a still life. If c is an oscillator and is not a still life we call c a proper oscillator.

A glider is a configuration c such that cn is a proper translation of c for some n>0.

Our definition of cellular automaton is a simple derivative of the one given in Codd (1968). The only difference in scope is that Codd only allows grids of dimension 2 and requires the presence of a quiescent state, that is, a state v0 such that f(v0,...,v0)=v0. Moreover, Codd only allows configurations in which finitely many cells are non-quiescent, while our definition of configuration allows any assignment of states to cells.

Common dimensions and neighborhoods

In the approach that studies a small set of automata which are explicitly described the most common space is by far ℤ2. This space can be easily represented in a computer screen or in print, is easy to manipulate, and geometric intuition is applicable. Some explicitly described cellular automata on ℤ1 and ℤ3 have also been studied. A disadvantage of ℤ1 is that information transfer requires many path crossings. In ℤ3 path crossings can be entirely avoided, but is harder to represent than ℤ1 and ℤ2. The most common neighbourhoods of CA in ℤ2 are shown below.

Representation of the hexagonal neighbourhood on the square tessellation.

For each dimension n≥1 and radius r≥0 we define the corresponding neighbourhoods:

  • The generalized von Neumann neighbourhood is the set {x∈ℤn|(MAX0≤in-1|xi|)<r}.
  • The generalized Moore neighbourhood is the set {x∈ℤn|(Σ0≤in-1|xi|)<r}.
  • The Euclidean neighbourhood is the set {x∈ℤn|(√Σ0≤in-1xi2)<r}.

See Gallery of neighbourhoods illustrations of some instances in ℤ2.

Other tesselations, such as the triangular[1] and Cairo pentagonal tesselations, have been investigated; the former can be simulated on the square grid using 4 states that divide each cell into two right triangles.[2]

Generalizations and topological characterization

Our definition is enough to describe most of the cellular automata in which explicitly described configurations are studied. In particular it handles as expected the elementary cellular automata, CA on the Euclidean square tessellation (including all life-like CA and all non-totalistic life-like CA) and the Euclidean hexagonal tessellation. Furthermore, CA on the Euclidean triangular tessellation can be handled when proper care is taken. However, there exist objects which are cellular automata according to our informal description, but can not be defined as such in our formal definition. An example is cellular automata in hyperbolic tessellations (Margenstern, 2013). A very general definition of cellular automata is given in Moriceau (2011) and a further generalization is given in Wacker (2016). Interestingly, Wacker's definition uses amenable groups. Both amenable groups and cellular automata were introduced by the same man: John von Neumann.

A remarkable result, the Curtis-Hedlund-Lyndon-Richardson (CHLR) theorem, relates cellular automata theory with topology and dynamical system theory. An informal statement is given as follows: Let the set of states be given the discrete topology and the configuration space be given the Tikhonov topology; then the global transition functions of the cellular automata over the configuration space are exactly those functions which are continuous and commute with the translations of the cellular space. In particular, the CHLR theorem holds for our definition of CA. Informally we state that the CHLR theorem holds for definitions of CA where the set of states is required to be finite, but if the set of states is allowed to be infinite, the set of allowable neighborhoods must be expanded or a further constraint must be imposed on continuous functions so that an analogous result holds (Ceccherini-Silberstein 2010; Sobottka 2015). Generally when a novel definition of cellular automaton is presented a corresponding version of the CHLR theorem is proved in the same treatise.

The CHLR theorem was demonstrated independently by Hedlund (1969) (in this paper credit is given to Curtis and Lyndon in addition to the author) and Richardson (1972). Neither of these papers use the term “cellular automaton”. Nonetheless the systems they study are, respectively, 2-dimensional deterministic cellular automata and n-dimensional non-deterministic cellular automata.

Block cellular automata

In the above definitions of cellular automata, the transition function takes the state of a set of possibly many cells and gives the next state for a single cell. Block cellular automata (BCA) use an alternative approach. In a BCA each configuration is augmented with a partition of the sets of cells into subsets of of finite size. Call this partition p(c) for any configuration c. The local transition function takes the state of all the cells in an element of p(c) and generates a new state for all those cells, instead of only for a single cell. The partitioning of a configuration c needs not be the same as c1. If that was the case, the state of one cell could never affect the state of any cell outside its partition. However, the partitioning must be independent of the states of cells. In the context of BCA the partitioning scheme is called the neighborhood.

The motivation to study block cellular is the ease with which reversible global transition functions can be generated. The local transition rule of a BCA is injective if and only if it is bijective. Any bijective local transition function generates a bijective global transition function. All block cellular automata can be transformed into equivalent classical cellular automata at the expense of adding more states or expanding the neighborhood.

The most commonly studied partition is the Margolous neighborhood. This partitioning scheme is defined for ℤ2. The partition is a grid of blocks of cells of size 2×2. The blocks are shifted one cell vertically and horizontally after each time step; therefore the partition repeats with period 2. In other words, given a configuration c, the cell space is partitioned along the green-blue lines to compute cn+1 from cn for even n and along the red lines to compute cn+1 from cn for odd n.

File:Margolous neighbourhood.png
The Margolous neighbourhood.
File:Effective Margolous neighbourhood of a single cell.png
The neighborhood of a single cell effectively switches as shown every time step.

Self-replicating configurations

Informally, a configuration that creates a copy of itself after some number of generations is called a replicator.

John von Neumann investigated the possibility of building a self-replicating machine. He originally considered a mechanical approach, but decided that this was too hard to control. With the help of Stanislaw Ulam, he designed a new mathematical abstraction, the cellular automaton, in order to create a replicator. His CA was made in the late 1940s and is complex. It operates on the Von Neumann neighbourhood (a cell and its four orthogonally connected neighbours), and has 29 states. It is described in von Neumann, Burks (1966).

Subsequent to the von Neumann's cellular automaton new cellular automata have been produced capable of self-replication and universal computation with fewer states and using the same (von Neumann) neighborhood. Results include Codd (1968) with 8 states, Banks (1971) with 4 states and Serizawa (1987) with 3 states. As of 2017, Serizawa's CA appears to be the simplest (in terms of neighborhood size×number of states) cellular automaton known to have a non-trivial replicator.

Langton (1984) constructed a cellular automaton and a replicator. His cellular automaton is a simplification of Codd's. However, Langton's CA was not intended to support universal computation. The simplicity of the configuration is possible because of a novel method of self-replication. The replicator consists of a loop with circulating cell states that encode instructions to construct a new arm, then turn 90° and repeat until a new loop is formed. The new loop is then filled with the same circulating information and the connection between it and the loop that generated it is severed. The parent loop continues to build copies until no more space is available, then it becomes a still life.

Nehaniv (2002) presented a method that allows the transformation of conventional (synchronous) cellular automata to an equivalent asynchronous cellular automata (a case not covered by our definition above). In the same paper, a self-reproducing configuration is presented which is based on the described procedure applied to Langton's CA.

Conway's Game of Life is known to be universal, with 2 states and the Moore neighbourhood. Conway did not design Life for this purpose, unlike von Neumann's, Codd's, Banks' and Serizawa's rules, so it is purely coincidental that Life supports replicators. The Spartan universal computer-constructor could replicate, given a sufficient program tape. Between 2010 and 2017 much more efficient construction mechanisms have been developed that can be used for self-replication, but to date only a limited one-dimensional example has actually been completed (the linear propagator).

Formal definition

There are several possible non-equivalent definitions of self-replicators. Moore (1962) proposed a simple definition which does not attempt to exclude trivial cases (although Moore wrote “self-reproduction”, we assume that it synonymous with “self-replication”). However, his definitions of self-replicator is limited to the same cellular automata and configurations allowed by the definition of Codd (1968). Our definition is a slight generalization of Moore's definition to cover all the configurations allowed by our definition.

Not all of the self-replicators mentioned above meet our formal definition. Langton's self-replicating loop and the classical HighLife replicator meet our definition. Typically the configurations in which each copy of the initial configuration only generates one copy but does not returns to the initial state after finishing do not meet our definition.

Definition: Let (ℤn,S,N,f) be a cellular automaton. Let c be a configuration such that for some sS the set X={a∈ℤn|c(a)≠s} is finite. We say that c is a finite configuration, s is a background state of c and X is a support of c.

Theorem: Let c be a finite configuration, then there is a unique background state and support of c.

Let v and v′ be background states of c. Let X be the set of all cells a such that c(a)≠v and respectively for X′ and v′. The set ℤn\(XX′) is non-empty because ℤn is infinite and XX′ is finite. Let x∈ℤn\(XX′). By the properties of set union and complement we have x∈ℤn\X and x∈ℤn\X′; by definition of X and X′ we have x=v and x=v′; therefore v=v′. Again from the definition of X and X′ it follows that X=X′.

Definition: Let c be a finite configuration. We write bg(c) for the background state of c and we write su(c) for the support of c.

Definition: Let c and c′ be finite configurations such that bg(c)=bg(c′). If su(c)∩su(c′)=∅ we say that c is disjoint from c′. If su(c)⊂su(c′) and for all asu(c) we have c(a)=c′(a) then we say that ccontains c.

Definition: Let c and c′ be configurations. We say that ccontains at least n copies if c if there exist a set X of pairwise disjoint translations of c and for each xX, c contains x.

Definition: A configuration c is called a self-replicator if for any n≥1 there exist a t≥0 such that ct contains at least n disjoint copies of c.

Definition: Let c and c be a configuration. Let n≥0 be an integer. If c′ contains at least n copies of c and for any integer k>n it is not the case that c′ contains at least k copies of c then we say that ccontains exactly n copies of c.

Life-like cellular automata

Also see: Totalistic Life-like cellular automaton

A cellular automaton is said to be Life-like if it meets the following four criteria:

  • It has two dimensions (i.e., n=2).
  • It has two states, usually called OFF and ON (i.e., |S|=2).
  • The neighbourhood used is the Moore neighbourhood.
  • The new state of a cell in the next generation can be expressed as a function of the number of cells in its neighbourhood that are in the ON state and the cell's own state; that is, the rule is outer totalistic (also called semitotalistic).

This class of cellular automata is named for Conway's Game of Life, the most famous cellular automaton, which Life-like cellular automata mimic. Many different terms are used to describe this class of cellular automata; it is also common to refer to it as the "Life family" or to simply use phrases like "similar to Life".

Rules

Rules are typically expressed as rulestrings in B/S notation, with two lists of numbers giving the live neighbour counts that cause a dead cell to be born or a live cell to survive, respectively; Conway's Game of Life has the rulestring B3/S23.

There are 262144 (= 218) distinct Life-like rules. Each rule has a complementary rule which behaves identically under on-off reversal; namely the rule in which birth occurs on all N except those for which 8-N is a survival condition in the original rule, and survival occurs on all N except those for which 8-N is a birth condition in the original rule. For example, the rule complementary to Conway's Life is 01234678/0123478. This however does not quite halve the number of effectively distinct rules, as there are 512 (= 29) self-complementary rules which are unaffected by on-off reversal.

Some straightforward inferences on the behavior of different kinds of rules can be made:

  • In all rules where the lowest birth condition is 1 neighboring ON cell, all finite patterns grow at the speed of light in all directions. No still lifes, oscillators or spaceships are possible in these rules. Several have replicators, however. There are 65536 (= 216) rules of the B1 type.
  • All rules where the lowest birth condition is 2 neighboring ON cells are exploding or expanding in character; this is largely due to the fact that a domino at the corner of a pattern will give rise to a new domino, also located at the corner of the daughter pattern. Spaceships (such as the moon) and oscillators (such as the duoplet) do exist in many of these rules. There are 32768 (= 215) rules of the B2 type.
  • All rules where the lowest birth condition (if any) is 4 or more neighboring ON cells are stable in character, since no patterns ever grow beyond their initial bounding box. In particular, no spaceships can exist. There are 16384 (= 214) rules of the B4+ type.
  • In all rules where the lowest birth condition is 0 neighboring ON cells, and the highest survival condition is 8 neighboring ON cells, the vacuum is unstable and will be immediately filled (and remain filled) with ON cells; thus, there are no patterns that remain finite. All of these rules have distinct complementary rules, and they are not commonly studied on their own.
  • This leaves 16384 rules in which the lowest birth condition is 3 neighboring ON cells, as well as 65536 rules in which the lowest birth condition is 0 neighboring cells, and 8 neighbors is not a survival condition. All chaotic rules must fall in either of these two areas of the rulespace. Most well-studied examples fall in the first one, since for long no commonly available software existed that could simulate the evolution of rules containing B0.

Generalizations

Main articles: Non-totalistic Life-like cellular automaton, Non-isotropic Life-like cellular automaton, Generations, Larger than Life

Various generalizations of Life-like cellular automata are possible. In non-totalistic (but isotropic) rules, the transition function considers not just the number of cells in a given cell's neighborhood but also their relative alignment; for example, a cell might be born if bordered by three live cells in a row, but not by three live cells in other configurations. Non-totalistic rules are described using Hensel notation, an extension of B/S notation additionally describing allowed or forbidden configurations.

In non-isotropic rules, the transition function additionally considers the absolute placement of a given cell's neighborhood; for example, a cell might be born if it is bordered by two live neighbors on the north and northeast, but not if it is bordered by two live neighbors on the south and southwest. Non-isotropic rules are described using MAP strings, a notation unrelated to B/S notation.

In Generations rules, additional states are introduced, and cells that do not survive into the next generation instead progress through the subsequent states before dying. Cells in these additional states do not count as live neighbors for the purpose of evolution.

In Larger than Life rules, the size of a cell's neighborhood is extended to include cells with a distance greater than one. As in Generations rules, non-surviving cells may decay through additional states instead of dying outright.

Well-known life-like cellular automata

Main article: List of Life-like cellular automata

The following table lists life-like cellular automata that are particularly well-known or well-studied.

Rulestring Name Description
B1357/S1357 Replicator A rule in which every pattern is a replicator.
B1357/S02468 Fredkin A rule in which, like Replicator, every pattern is a replicator.
B2/S Seeds An exploding rule in which every cell dies in every generation. It has many simple orthogonal spaceships, though it is in general difficult to create patterns that don't explode.
B2/S0 Live Free or Die An exploding rule in which only cells with no neighbors survive. It has many spaceships, puffers, and oscillators, some of infinitely extensible size and period.
B3/S012345678 Life without death An expanding rule that produces complex flakes. It also has important ladder patterns.
B3/S12 Flock A rule which rapidly decays into small still lifes and oscillators.
B3/S1234 Mazectric An expanding rule that crystalizes to form maze-like designs that tend to be straighter (ie. have longer "halls") than the standard maze rule.
B3/S12345 Maze An expanding rule that crystalizes to form maze-like designs.
B3/S23 Conway's Life A chaotic rule that is by far the most well-known and well-studied. It exhibits highly complex behavior.
B36/S125 2x2 A chaotic rule with many simple still lifes, oscillators and spaceships. Its name comes from the fact that it sends patterns made up of 2x2 blocks to patterns made up of 2x2 blocks.
B36/S23 HighLife A chaotic rule very similar to Conway's Life that is of interest because it has a simple replicator.
B368/S245 Move A rule in which random patterns tend to stabilize extremely quickly. Has a very common slow-moving spaceship and slow-moving puffer.
B3678/34678 Day & Night A stable rule that is symmetric under on-off reversal. Many patterns exhibiting highly complex behavior have been found for it.
B37/S23 DryLife An explosive rule that resembles the regular Game of Life, but the weighted spaceships do not function, and there exists 9c/28 orthogonal technology.
B38/S23 Pedestrian Life A chaotic rule that strongly resembles regular Life, with many exciting natural technologies.

References

  • Banks, E. R. (1971) Information processing and transmission in cellular automata.
  • Ceccherini-Silberstein, T.; Coornaert, M. (2010) Cellular Automata and Groups. DOI: 10.1007/978-3-642-14034-1. ISBN: 978-3-642-14033-4, 978-3-642-14034-1.
  • Codd, E. F. (1968) Cellular Automata. No ISBN. WorldCat OCLC number: 637978742.
  • Hedlund, G. A. (1969) Endomorphisms and Automorphisms of the Shift Dynamical System. DOI: 10.1007/BF01691062.
  • Langton, C. G. (1984) Self-reproduction in cellular automata. DOI: 10.1016/0167-2789(84)90256-2.
  • Margenstern, M. (2013) Small Universal Cellular Automata in Hyperbolic Spaces: A Collection of Jewels.
  • Moore, E. F. (1962) Machine models of self-reproduction in Mathematical Problems in the Biological Sciences. DOI: 10.1090/psapm/014/9961.
  • Moriceau, S. (2011) Cellular automata on a G-set. arXiv: 1105.5335 [math.DS].
  • Nehaniv, C. E. (2002) Self-Reproduction in Asynchronous Cellular Automata in Proceedings 2002 NASA/DoD Conference on Evolvable Hardware. DOI: 10.1109/eh.2002.1029854.
  • Richardson, D. (1972) Tessellation with Local Transformations. DOI: 10.1016/S0022-0000(72)80009-6.
  • Serizawa, T. (1987) Three-State Neighbor Cellular Automata Capable of Constructing Self-Reproducing Machines. DOI: 10.1002/scj.4690180404.
  • Sobottka, M.; Gonçalves, D. (2015) A note on the definition of siding block codes and the Curtis-Hedlund-Lyndon Theorem. arXiv: 1507.02180 [math.DS].
  • von Neumann, J.; Burks, A. W. (1966) Theory of Self-Reproducing Automata. No ISBN. WorldCat OCLC number: 7298386.
  • Wacker, S. (2016) Cellular Automata on Group Sets and the Uniform Curtis-Hedlund-Lyndon Theorem. DOI: 10.1007/978-3-319-39300-1_15. In Cellular Automata and Discrete Complex Systems. AUTOMATA 2016.

External links

Cellular automata rules lexicon at Mirek Wójtowicz's Cellebration page

Cellular Automaton at Wolfram Mathworld Totalistic Cellular Automaton at Wolfram Mathworld