Difference between revisions of "Cellular automaton"

From LifeWiki
Jump to navigation Jump to search
(Undo revision 13169 by 145.7.91.95 (Talk))
(Use LinkMirek)
(22 intermediate revisions by 11 users not shown)
Line 1: Line 1:
{{Glossary}}
{{Glossary}}
A '''cellular automaton''' is a certain class of mathematical objects of which [[Conway's Game of Life]] is an example. It consists of a number of things:
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. It consists of a number of things:
* A positive integer n which is the dimension of the cellular automaton
* A positive integer n which is the dimension of the cellular automaton
* A finite set of states S, with at least two members
* A finite set of states S, with at least two members
* A state for the whole cellular automaton is obtained by assigning an element of S to each point of the n-dimensional lattice Z<sup>n</sup> (where Z is the set of all integers), known as [[cell]]s
* A state for the whole cellular automaton is obtained by assigning an element of S to each point of the n-dimensional lattice Z<sup>n</sup> (where Z is the set of all integers), known as [[cell]]s
* The concept of a neighbourhood. The neighbourhood N of the origin is some finite (nonempty) subset of Z<sup>n</sup>. The neighbourhood of any other cell is obtained in the obvious way by translating that of the origin.
* The concept of a neighbourhood. The neighbourhood N of the origin is some finite (nonempty) subset of Z<sup>n</sup>. The neighbourhood of any other cell is obtained in the obvious way by translating that of the origin.
* A transition rule, which is a function from S<sup>N</sup> to S (that is to say, for each possible state of the neighbourhood the transition rule specifies some cell state).
* A transition rule, which is a function from S(n) to S (that is to say, for each possible state of the neighbourhood the transition rule specifies some cell state).


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.
Line 14: Line 14:


==Self-replication in cellular automata==
==Self-replication in cellular automata==
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.
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==
Line 28: Line 24:
* 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'' (or ''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===
Line 36: Line 32:


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.
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.
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 life]]s, [[oscillator]]s or [[spaceship]]s are possible in these rules. Several have [[replicator]]s, however. There are 65536 (= 2<sup>16</sup>) 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 [[User:Methodood/Duoplet|duoplet]]) do exist in many of these rules. There are 32768 (= 2<sup>15</sup>) 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 (= 2<sup>14</sup>) 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 (empty space)|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.
===Non-totalistic rules===
:''Main article: [[Non-totalistic Life-like cellular automaton]]''
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===
===Well-known Life-like cellular automata===
There are 262144 (2<sup>18</sup>) distinct Life-like rules, which is far too many to list here. The following table lists rules that are particularly well-known or well-studied. This table uses S/B notation for rulestrings.
:''Main article: [[List of Life-like cellular automata]]''
 
The following table lists rules that are particularly well-known or well-studied.  


{| class="wikitable"
{| class="wikitable"
! Rulestring !! Name !! Description
! Rulestring !! Name !! Description
|-
|-
| 1/1 || [[Gnarl]] || A simple exploding rule that forms complex patterns from even a single live cell.
| B1357/S1357 || [[Replicator (CA)|Replicator]] || A rule in which every pattern is a [[replicator]].
|-
| 1357/1357 || [[Replicator (CA)|Replicator]] || An exploding rule in which every pattern is a [[replicator]].
|-
| 02468/1357 || [[Fredkin]] || An exploding rule in which, like [[Replicator (CA)|Replicator]], every pattern is a [[replicator]].
|-
| /2 || [[Seeds]] || An exploding rule in which every [[cell]] dies in every [[generation]]. It has many simple orthogonal [[spaceship]]s, though it is in general difficult to create patterns that don't explode.
|-
| 0/2 || [[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.
|-
| /234 || [[Serviettes]] || An exploding rule in which every cell dies every generation (like seeds). This rule is of interest because of the fabric-like beauty of the patterns that it produces.
|-
| 012345678/3 || [[Life without death]] || An expanding rule that produces complex flakes. It also has important [[ladder]] patterns.
|-
| 1234/3 || [[Mazectric]] || An exploding rule that crystalizes to form maze-like designs that tend to be straighter (ie. have longer "halls") than the standard maze rule.
|-
| 12345/3 || [[Maze]] || An exploding rule that crystalizes to form maze-like designs.
|-
| 23/3 || [[Conway's Game of Life|Conway's Life]] || A chaotic rule that is by far the most well-known and well-studied. It exhibits highly complex behavior.
|-
| 45678/3 || [[Coral]] || An exploding rule in which patterns grow slowly and form coral-like textures.
|-
| 34/34 || [[34 Life]] || An exploding rule that was initially thought to be a stable alternative to [[Conway's Game of Life|Conway's Life]], until computer simulation found that most patterns tend to explode. It has many small oscillators and a simple period 3 orthogonal spaceship.
|-
| 4567/345 || [[Assimilation]] || A very stable rule that forms permanent diamond-shaped patterns with partially filled interiors.
|-
| 5/345 || [[Long Life]] || A stable rule that gets its name from the fact that it has many simple extremely high period oscillators.
|-
|-
| 5678/35678 || [[Diamoeba]] || A chaotic pattern that forms large diamonds with chaotically oscillating boundaries. Known to have quadratically-growing patterns.
| B1357/S02468 || [[Fredkin]] || A rule in which, like [[Replicator (CA)|Replicator]], every pattern is a [[replicator]].
|-
|-
| 1358/357 || [[Amoeba]] || A chaotic rule that is well balanced between life and death; it forms patterns with chaotic interiors and wildly moving boundaries.
| B2/S || [[Seeds]] || An exploding rule in which every [[cell]] dies in every [[generation]]. It has many simple orthogonal [[spaceship]]s, though it is in general difficult to create patterns that don't explode.
|-
|-
| 238/357 || [[Pseudo Life]] || A chaotic rule with evolution that resembles Conway's Life, but few patterns from Life work in this rule because the [[glider]] is unstable.
| 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.
|-
|-
| 125/36 || [[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.
| B3/S012345678 || [[Life without death]] || An expanding rule that produces complex flakes. It also has important [[ladder]] patterns.
|-
|-
| 23/36 || [[HighLife]] || A chaotic rule very similar to [[Conway's Game of Life|Conway's Life]] that is of interest because it has a simple [[replicator]].
| B3/S12 || [[Flock]] || A rule which decays into small still lifes and oscillators
|-
|-
| 245/368 || [[Move]] || A rule in which random patterns tend to stabilize extremely quickly. Has a very common slow-moving spaceship and slow-moving [[puffer]].
| 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.
|-
|-
| 235678/3678 || [[Stains]] || A stable rule in which most patterns tend to "fill in" bounded regions. Most nearby rules (such as coagulations) tend to explode.
| B3/S12345 || [[Maze]] || An expanding rule that crystalizes to form maze-like designs.
|-
|-
| 34678/3678 || [[Day & Night]] || A stable rule that is symmetric under on-off reversal. Many patterns exhibiting highly complex behavior have been found for it.
| B3/S23 || [[Conway's Game of Life|Conway's Life]] || A chaotic rule that is by far the most well-known and well-studied. It exhibits highly complex behavior.
|-
|-
| 235678/378 || [[Coagulations]] || An exploding rule in which patterns tend to expand forever, producing a thick "goo" as it does so.
| 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.
|-
|-
| 2345/45678 || [[Walled cities]] || A stable rule that forms centers of pseudo-random activity separated by walls.
| B36/S23 || [[HighLife]] || A chaotic rule very similar to [[Conway's Game of Life|Conway's Life]] that is of interest because it has a simple [[replicator]].
|-
|-
| 35678/4678 || [[Vote 4/5]] || A modification of the standard Gérard Vichniac voting rule, also known as "Anneal", used as a model for majority voting.
| 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]].
|-
|-
| 45678/5678 || [[Vote]] || Standard Gérard Vichniac voting rule, also known as "Majority", used as a model for majority voting.
| 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.
|}
|}


==External links==
==External links==
*[http://psoup.math.wisc.edu/mcell/rullex_life.html Cellular automata rules lexicon] at Mirek's Cellebration
{{LinkMirek|ca_rules.html|title=Cellular automata rules lexicon}}
*[http://www.argentum.freeserve.co.uk/lex_c.htm#cellularautomaton Cellular automaton] at the Life Lexicon
{{LinkLexicon|lex_c.htm#cellularautomaton}}
*[http://code.google.com/p/ruletablerepository/ Rule Table Repository]
*[https://github.com/gollygang/ruletablerepository/wiki/TheRules Rule Table Repository]

Revision as of 12:43, 12 October 2016

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. It consists of a number of things:

  • A positive integer n which is the dimension of the cellular automaton
  • A finite set of states S, with at least two members
  • A state for the whole cellular automaton is obtained by assigning an element of S to each point of the n-dimensional lattice Zn (where Z is the set of all integers), known as cells
  • The concept of a neighbourhood. The neighbourhood N of the origin is some finite (nonempty) subset of Zn. The neighbourhood of any other cell is obtained in the obvious way by translating that of the origin.
  • A transition rule, which is a function from S(n) to S (that is to say, for each possible state of the neighbourhood the transition rule specifies some cell state).

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 Zn, 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 centred on that cell, which is known as its Moore neighbourhood.

Self-replication in cellular automata

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

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 neighborhood used is the Moore neighborhood; it consists of the eight (orthogonally and diagonally) adjacent cells to the one under consideration and (possibly) the cell itself.
  • 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).

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

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.

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 (= 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) 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.

Non-totalistic rules

Main article: Non-totalistic Life-like cellular automaton

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

Main article: List of Life-like cellular automata

The following table lists rules 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 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.

External links

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