LifeWiki - User contributions [en]

Cellular automaton

2015-07-09T22:26:17Z

Tim Hutton: The Rule Table Repository has moved to github.

{{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. 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 [[cell]]s
* 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 generalizations 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 (= 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 [[User:Methodood/Duoplet|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 (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.

===Well-known Life-like cellular automata===
The following table lists rules that are particularly well-known or well-studied. This table uses S/B notation for rulestrings.

{| class="wikitable"
! Rulestring !! Name !! Description
|-
| 1/1 || [[Gnarl]] || A simple exploding rule that forms complex patterns from even a single live cell.
|-
| 1357/1357 || [[Replicator (CA)|Replicator]] || A rule in which every pattern is a [[replicator]].
|-
| 02468/1357 || [[Fredkin]] || A 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.
|-
| 023/3 || [[DotLife]] || An exploding rule closely related to Conway's Life. The [[B-heptomino]] is a common infinite growth pattern in this rule, though it can be stabilized into a spaceship.
|-
| 012345678/3 || [[Life without death]] || An expanding rule that produces complex flakes. It also has important [[ladder]] patterns.
|-
| 1234/3 || [[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.
|-
| 12345/3 || [[Maze]] || An expanding 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 simple period 3 orthogonal and diagonal spaceships.
|-
| 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.
|-
| 1358/357 || [[Amoeba]] || A chaotic rule that is well balanced between life and death; it forms patterns with chaotic interiors and wildly moving boundaries.
|-
| 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.
|-
| 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.
|-
| 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]].
|-
| 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]].
|-
| 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.
|-
| 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.
|-
| 23/37 || [[DryLife]] || An exploding rule closely related to Conway's Life, named after the fact that the [[standard spaceship]]s bigger than the [[glider]] do not function in the rule. Has a small puffer based on the [[R-pentomino]], which resembles the [[switch engine]] in the possibility of combining several to form a spaceship.
|-
| 235678/378 || [[Coagulations]] || An exploding rule in which patterns tend to expand forever, producing a thick "goo" as it does so.
|-
| 2345/45678 || [[Walled cities]] || A stable rule that forms centers of pseudo-random activity separated by walls.
|-
| 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.
|-
| 45678/5678 || [[Vote]] || Standard Gérard Vichniac voting rule, also known as "Majority", used as a model for majority voting.
|}

==External links==
*[http://www.mirekw.com/ca/ca_rules.html Cellular automata rules lexicon] at Mirek's Cellebration
*[http://www.argentum.freeserve.co.uk/lex_c.htm#cellularautomaton Cellular automaton] at the Life Lexicon
*[https://github.com/gollygang/ruletablerepository/wiki/TheRules Rule Table Repository]

Universal computer

2015-07-09T22:24:27Z

Tim Hutton: The Rule Table Repository has moved to github.

{{Glossary}}
A '''universal computer''' in a [[cellular automaton]] is a system that can compute anything that a [http://en.wikipedia.org/wiki/Turing_machine Turing machine] can compute. A cellular automaton in which such a system exists is called '''universal'''. A universal computer may be either infinite or finite, but when combined with a [[universal constructor]], it is assumed to be finite.

==Universal computers in Life==
In 1982, [[John Conway]] proved in ''[[Winning Ways]]'' that the [[Game of Life]] has a (finite) universal computer, as well as a universal constructor. Proving the universality of a cellular automaton with simple rules was in fact Conway's aim in Life right from the start. The universal computer uses [[glider]] logic and a [[sliding block memory]], and the proof of its existence is also outlined in [[The Recursive Universe]].

In April 2000, [[Paul Rendell]] constructed a direct implementation of a [[Turing machine]].<ref>{{cite web|url=http://rendell-attic.org/gol/tm.htm|title=A Turing Machine in Conway's Game of Life|author=Paul Rendell|date=April 2, 2000}}</ref> This computer is infinite, as it requires an infinite length of tape for the Turing Machine.

In 2002, using [[Dean Hickerson]]'s [[sliding block memory]], [[Paul Chapman]] constructed an implementation of a Minsky Register Machine (a machine of the same capability as a Turing Machine), which he extended to a Universal Register Machine, a finite universal computer.<ref>{{cite web|url=http://www.igblan.free-online.co.uk/igblan/ca/|title=Life Universal Computer|author=Paul Chapman|date=November 11, 2002}}</ref>

In 2009, [[Adam P. Goucher]] built a [[Spartan universal computer-constructor]], which has three infinite binary memory tapes (program tape, data tape and marker tape). This allows data to be stored in linear space, rather than the exponential space that a Register Machine uses.

==Universal computers in other cellular automata==
David Eppstein and Dean Hickerson proved that [[236/35]] has a universal computer and universal constructor, using the same method of proof that Conway used to prove that Life is universal.<ref>{{cite web|url=http://www.ics.uci.edu/~eppstein/ca/b35s236/|title=B35/S236|author=D. Eppstein}}</ref>

Tim Hutton has implemented Codd's design for a universal computer in Codd's 8-state cellular automaton.<ref>{{cite web|url=https://github.com/GollyGang/ruletablerepository/wiki/CoddsDesign|title=Rule Table Repository|author=Tim Hutton}}</ref>

==References==
<references />

==External Links==
{{LinkLexicon|lex_u.htm#universalcomputer}}

Talk:Von Neumann neighbourhood

2015-07-09T22:21:40Z

Tim Hutton: The Rule Table Repository has moved to github.

Is there a Brooklyn neighborhood or a Queen's neighborhood? Does anyone know where this reference to taxicabs or New York bouroughs came from? Anyone who has ever wandered through Manhattan knows it's rectangular, not square. Do people in Australia, or Singapore or whereever know how New York is laid out? Why can't we respect Hamming, even though it was coding theory; or at least use L(1), L(2), L(infinite) and be Bourbakians.

Because Hamming distance, when generalised to the plane, is a different metric. All the points within a ''Hamming distance'' of one are the following:

.....o.....
.....o.....
.....o.....
.....o.....
ooooo*ooooo
.....o.....
.....o.....
.....o.....
.....o.....

This is obvious when the cells are converted into Cartesian coordinates -- these are the points that differ in only one coordinate.

Whereas the von Neumann neighbourhood refers to the orthogonally adjacent places, i.e. those within a ''Manhattan distance'' of one:

...........
...........
...........
.....o.....
....o*o....
.....o.....
...........
...........
...........

And for that matter, Manhattan distance is irrespective of whether the roads are in a rectangular or square arrangement; as long as all roads are '''orthogonal''', the distance will be the same: the sum of the horizontal distance and the vertical distance.

And Queen's neighbourhood would be slightly ambiguous -- chess players would assume that it refers to all cells in the vertical, horizontal and diagonal lines that run through the central cell.

Yes, Manhattan distance is L(1), but the common name is more intuitive.

Regards, [[User:Calcyman|Calcyman]] 16:54, 29 January 2010 (UTC)

:Let us not forget that Broadway runs diagonally across Manhattan. And anyone who bases a grid on a city map should beware Boston, whose streets arose from paving cow paths. However, one could wonder why this whole discussion of specialized neighbo(u)rhoods is in a Wikipedia devoted to Life, rather than in a more general context of cellular automata or dynamical systems; there is already a page dedicated to the general environment entitled "Neighborhood." Also, note the anomaly that the Hamming distance or whatever appears in a paragraph of an article on the ''von Neumann'' neighborhood referring to a property of a ''Moore'' neighborhood!

:Using Internet to try to find word or phrase origins, It seems that Minkowski started off around 1900, that the L(p)'s refer to Lebesque, and that Tchebycheff (or was it Cebysev?) used a minimax of greatest among the least for approximations. However, the question at hand is whether "manhattan" is the best adjective. True, ''L(p)'' sounds too mathematical for life enthusiasts; equivalently ''taxicab'' or ''manhattan'' is much too cute. The best solution might to be to suppress these pages until such time that a better and more coherent discussion is available for each of them.

:The broad subject would include not only the L(p) metric, of which only L(1) and L(infinity) seem pertinent, but sparse neighborhoods, historical neighborhoods, progressive neighborhoods, blocked neighborhoods, and so on. (Sparse to make iteration look more like composition, Historical to incorporate previous states of a cell, Progressive to incorporate recent changes in the formulation, Blocked to include Margolus, ..... )

::'''Manhattan distance''' is the most widely accepted term for the L(1) metric. Admittedly, the name might be slightly imprecise, but it's better than (ab)using '''Hamming distance''' in this context.

::As for the mistake on Wikipedia, I have also rectified that. Thanks for pointing that out; that's probably how it leaked on to the LifeWiki in the first place.

::The different 'neighbourhoods' you have mentioned (e.g. 'Historical') are not neighbourhoods per se, but rather entire classes of rules (with the exception of 'blocked', which is another term for a ''partitioning scheme''). Other ''neighbourhoods'' include the hexagonal neighbourhood (for the A2 lattice) and the three-dimensional analogues of the von Neumann and Moore neighbourhoods. For a comprehensive list of neighbourhoods, see the respective page on the Rule Table Repository: [https://github.com/gollygang/ruletablerepository/wiki/RoadMap]

:::Isn't the whole discussion of neighborhoods more complicated than it needs to be? Part of the specification of a cellular automaton is the set in which it operates, which is commonly a crystallographic lattice, such as the cartesian plane with integer coordinates; that's where the cellular part comes from. Since a mapping, which is part of the process, is to be iterated, a generational index, usually regarded as time, could be included as an adjunct to the space. That could result in implicit, as well as explicit, definitions. Note how many words just saying this takes up; ordinary language doesn't get this complicated, but likewise doesn't encompass all the wierd possibilities.

:::Once we've got the space, there are neighborhoods. Although they are just subsets, there is a uniformity requirement. If the space is a lattice, they are related by symmetry; primarily translation (think of shift commuting dynamical systems). The space coule be a Cayley tree, neighbors established by linkage; many alternatives exist.

:::So much for definitions. In practice a particular cellular automaton might be chosen and studied in detail. Conway's Life is one of them, owing its interest to the illusion that its evolution could be understood, creating much entertainment and diversion. A more feasible alternative to understanding all properties of all cellular automata. Naturally this inherent curiosity encompasses variants and extensions, with an attendant challenge of parameterizing the alternatives. So we classify: shape and relative sizes of neighborhoods, dimension of neighborhoods, and so on. But wouldn't it be nice if this could be done in an orderly fashion?

:::To reply to one statement: "Historical" does not refer to what some LifeEnthusiast might have done in the past; it refers to the ordering implied by iteration, and to a rule of evolution which accounts for a certain portion of previous states. Fredkin's reversible rules are an example of this, and indeed Life can be taken as the reference rule for creating a reversible rule. Unfortunately, although the new rule is reversible, Life is not what it reverses.

:::What is this Google repository (reference 1)? Have they slurped up cellular automata too? I didn't see half-integer neighborhoods.

::::The variety of spaces for a cellular automaton is vast, indeed (uncountably?) infinite. As well as lattice grids, such as the square lattice, hexagonal lattice and FCC lattice, there are uniform nonlattice grids (e.g. triangular), and even totally aperiodic tilings such as the Penrose tiling. Life on Penrose tilings has been investigated, and forms the basis for a 50-page chapter in the upcoming Life book (Andy Adamatzky, 2010). Not to mention Lorentzian or hyperbolic spaces.

::::Classifying this infinite abundance of possible spaces is difficult, and I doubt that a systematic way exists to do so. If you think that you've found such a method, test it against the possible counter-examples in the above paragraph. I suppose that one might have to approach Penrose tilings from the 'quasicrystal' angle: define a lattice in a certain number of dimensions, and a hyperplane to intersect it.

::::As you've mentioned, the next step is to classify the neighbourhoods for each possible space. The square lattice alone has a massive variety of neighbourhoods, including the Moore neighbourhood, von Neumann neighbourhood and Margolus partitioning scheme. Again, the Rule Table Repository provides a more comprehensive list of neighbourhoods.

::::"Historical", when applied to cellular automata, almost invariably applies to a rule where the cells retain a "history" of whether they have been alive at any time. "Historical Life" (invented by Dave Greene), for example, behaves identically to Life, but has a third state to record whether cells have ever been alive. Gliders leave behind tracks in this third state.

::::The Rule Table Repository is a website, initially set up by Tim Hutton, but co-administrated by myself and four others.

::::Exactly what do you mean by 'half-integer neighbourhoods'?