Difference between revisions of "Totalistic Life-like cellular automaton"

From LifeWiki
Jump to navigation Jump to search
(Mathworld link)
m (LinkWikipedia)
(10 intermediate revisions by 3 users not shown)
Line 14: Line 14:
|}
|}


There are precisely 2<sup>9</sup> = 512 different totalistic CAs, compared to 2<sup>18</sup> = 262,144 outer-totalistic CAs.{{refn|group=note|Although there 262,144 different outer-totalistic Life-like CAs, some of these are essentially the same in some precise sense. See [[Cellular automaton#Rules|Cellular automaton]] for more.}}  
There are precisely 2<sup>9</sup> = 512 different totalistic CAs, compared to 2<sup>18</sup> = 262,144 outer-totalistic CAs.{{refn|group=note|Although there 262,144 different outer-totalistic Life-like CAs, some of these are essentially the same in a natural sense; the number of essentially different rules is 131,328. See [[Cellular automaton#Rules|Cellular automaton]], [[Black/white reversal]] and [[Self-complementary]] for more.}}  


A given outer-totalistic Life-like CA is totalistic iff for any 1 &le; ''n''  &le; 8, a live cell survives with ''n - 1'' neighbors iff a dead cell gets born with ''n'' neighbors. For example, the automaton given by the [[rulestring]] B3/S2 is totalistic; any cell will be alive in the next generation if it has exactly three live cells (including the cell itself) in its neighborhood, and dead otherwise. [[Conway's Game of Life]] (B3/S23), on the other hand, is not totalistic: a live cell with three neighbors will survive to the next generation, but a dead cell with four neighbors will not get born.
A given outer-totalistic Life-like CA is totalistic iff for any 1 &le; ''n''  &le; 8, a live cell survives with ''n - 1'' neighbors iff a dead cell gets born with ''n'' neighbors. For example, the automaton given by the [[rulestring]] B3/S2 is totalistic; any cell will be alive in the next generation if it has exactly three live cells (including the cell itself) in its neighborhood, and dead otherwise. [[Conway's Game of Life]] (B3/S23), on the other hand, is not totalistic: a live cell with three neighbors will survive to the next generation, but a dead cell with four neighbors will not get born.
==Rulestrings==
Totalistic CAs are described by totalistic rulestrings: strings of digits specifying the live cell counts which will cause a given cell to be alive in the next generation. For example, [[Replicator 2]] (also called Fredkin) has the totalistic rulestring 13579; the equivalent rulestring in B/S notation is B1357/S02468.


==Etymology==
==Etymology==
Line 22: Line 25:


==Generalizations==
==Generalizations==
Totalistic and outer-totalistic CAs can be generalized in several straightforward ways: taking into account the relative (but not absolute) alignment of live cells in a cell's neighborhood yields [[non-totalistic Life-like cellular automaton|non-totalistic (isotropic) CAs]], while also considering the absolute alignment yields [[non-isotropic Life-like cellular automaton|non-isotropic CAs]].
Totalistic and outer-totalistic CAs can be generalized in several straightforward ways: taking into account the relative (but not absolute) alignment of live cells in a cell's neighborhood yields [[isotropic non-totalistic Life-like cellular automaton|non-totalistic (isotropic) CAs]], while also considering the absolute alignment yields [[non-isotropic Life-like cellular automaton|non-isotropic CAs]].
 
They can also be generalized to larger neighbourhoods. [[Golly]] can simulate [[Larger than Life|a small selection of these rules]] if the birth and death conditions are all subsequent, and [[apgsearch]] v4.63 and above are able to search any rule up to a range of 5.<ref>{{LinkForumThread|format = ref|title = Re: apgsearch v4.0|author = Adam P. Goucher|date = November 6, 2018|accessdate = November 20, 2018|p = 65439}}</ref> LifeViewer can simulate these from ranges 1 to 500, on Moore, von Neumann and circular (but not hexagonal) neighbourhoods.


==Also see==
==Also see==
Line 33: Line 38:
==Notes==
==Notes==
<references group="note" />
<references group="note" />
==References==
<references />


==External links==
==External links==
{{LinkWikipedia|Life-like_cellular_automaton|name=Life-like cellular automaton}}
{{LinkMathworld|TotalisticCellularAutomaton.html|pagename=Totalistic Cellular Automaton}}
{{LinkMathworld|TotalisticCellularAutomaton.html|pagename=Totalistic Cellular Automaton}}


[[Category:Cellular automata| List of Life-like cellular automata]]
[[Category:Cellular automata]]
[[Category:Life-like cellular automata| List of Life-like cellular automata]]
[[Category:Life-like cellular automata]]
__NOTOC__
__NOTOC__

Revision as of 00:38, 25 June 2019

Totalistic Life-like cellular automaton can refer to two related but distinct classes of cellular automata.

Most precisely, a Life-like cellular automaton is said to be totalistic if the new state of a (live or dead) cell in the next generation can be expressed as a function of the total number of live cells in its neighborhood, including the cell itself.

In common parlance, totalistic is also often (but incorrectly) used as a synonym for outer-totalistic / semi-totalistic, meaning that the new state of a cell is a function of both the total number of live cells surrounding the cell, and the state of the cell itself. The rest of this article will use the previous, precise definition.

The two definitions differ in that in the second case, the transition function may afford special consideration to the state of the cell itself. For example, the following two configurations may evolve differently in an outer-totalistic CA, but must be treated the same by a totalistic CA:

File:Neighborhood 2a.png File:Neighborhood 3i dead.png

There are precisely 29 = 512 different totalistic CAs, compared to 218 = 262,144 outer-totalistic CAs.[note 1]

A given outer-totalistic Life-like CA is totalistic iff for any 1 ≤ n ≤ 8, a live cell survives with n - 1 neighbors iff a dead cell gets born with n neighbors. For example, the automaton given by the rulestring B3/S2 is totalistic; any cell will be alive in the next generation if it has exactly three live cells (including the cell itself) in its neighborhood, and dead otherwise. Conway's Game of Life (B3/S23), on the other hand, is not totalistic: a live cell with three neighbors will survive to the next generation, but a dead cell with four neighbors will not get born.

Rulestrings

Totalistic CAs are described by totalistic rulestrings: strings of digits specifying the live cell counts which will cause a given cell to be alive in the next generation. For example, Replicator 2 (also called Fredkin) has the totalistic rulestring 13579; the equivalent rulestring in B/S notation is B1357/S02468.

Etymology

The word "totalistic" stems from the fact that evolution in a totalistic CA depends only on the total number of live cells in a given cell's neighborhood; similarly, in outer-totalistic CAs, evolution depends on the total number of outer cells, rather than their specific alignment. The word "semi-totalistic" expresses that an outer-totalistic CA, while not necessarily totalistic, is not entirely non-totalistic either: the transition function still depends on some certain total number of live cells.

Generalizations

Totalistic and outer-totalistic CAs can be generalized in several straightforward ways: taking into account the relative (but not absolute) alignment of live cells in a cell's neighborhood yields non-totalistic (isotropic) CAs, while also considering the absolute alignment yields non-isotropic CAs.

They can also be generalized to larger neighbourhoods. Golly can simulate a small selection of these rules if the birth and death conditions are all subsequent, and apgsearch v4.63 and above are able to search any rule up to a range of 5.[1] LifeViewer can simulate these from ranges 1 to 500, on Moore, von Neumann and circular (but not hexagonal) neighbourhoods.

Also see

Notes

  1. Although there 262,144 different outer-totalistic Life-like CAs, some of these are essentially the same in a natural sense; the number of essentially different rules is 131,328. See Cellular automaton, Black/white reversal and Self-complementary for more.

References

  1. Adam P. Goucher (November 6, 2018). Re: apgsearch v4.0 (discussion thread) at the ConwayLife.com forums

External links

Totalistic Cellular Automaton at Wolfram Mathworld