Information icon.svg Please vote in the 2017 board of trustees election. The cabal thanks you for your service. There are 6 more days left to vote.

Cellular automaton

From RationalWiki
(Redirected from Cellular automata)
Jump to: navigation, search
Part of a
convergent series on

Mathematics
link=:category:
2+2=4

A cellular automaton is a model consisting of a discrete number of states in a regular grid. Time is also discrete, and the state of a cell at time t is a function of the states of its neighbors at time t - 1. For example, in Conway's Game of Life, a cell can either be "alive" (coloured black) or "dead" (coloured white, it can also be taken as the cell just not being there), the cell then changes states based on the number of living cells right next to it. However, more complex rules can exist, such as rules that allow cells to be in a variety of different states besides just "alive" and "dead" (usually represented by different coloured cells).

Relationship to evolution[edit]

See the main article on this topic: Evolution

Besides being an amusing mathematical game, certain patterns in cellular automata have simulated reproduction and evolution. There are many instances of self-replicating patterns in cellular automata, the first being made in a variation of John von Neumann's cellular automaton. This replicator is very large and takes more than 1010 steps to replicate, but since then other patterns have been discovered, such as Langton's loops, sheaths which reproduce by extending a pseudopod. One variety of this, the evoloop, can be seen to evolve. As competition is generally for space, they tend towards smaller and smaller loops.[1] Evoloops can be formed from random patterns, a theoretical example of abiogenesis.[2]

Richard Dawkins also explored cellular automata as a model for evolution in his book The Blind Watchmaker (1986).

Conway's Game of Life[edit]

A "Gospers glider gun" in the Game of Life: an example of simple rules producing "gliders" ad infinitum

Conway's Game of Life is one of the more famous examples of cellular automata amongst mathematicians and computer geeks. It creates animated cellular patterns based on a strict set of rules:

  1. Any live cell with fewer than two live neighbours dies (due to loneliness).
  2. Any live cell with more than three live neighbours dies (due to overpopulation).
  3. Any live cell with two or three live neighbours lives, unchanged, to the next generation.
  4. Any dead cell with exactly three live neighbours becomes a live cell.[3]

In other words, unlike in other cellular automata, cells in Conway's Game of Life have only two states, alive and dead.[4] In spite of this, many complex patterns have been found in Life. On November 23, 2013, an explicit example of replicator in Conway's Game of Life was built, consisting of 145,306 live cells.[5] A small replicator has been found in HighLife, one of the variants of Conway's Game of Life where the rules above are altered.[6]

Life imitates "Life"[edit]

In 2017, it was discovered that the patterns on the ocellated lizard (Timon lepidus) change as it grows in a manner comparable to that of a cellular automaton.[7][8]

See also[edit]

External links[edit]

  • Evoloop animations
  • Golly, a program which supports multiple automata, and comes with a selection of interesting patterns.
  • A Conway's Game of Life simulator (java)

References[edit]

  1. An animation of evoloops evolving
  2. Evoloop abiogenesis
  3. Because we all know it takes three people to form a babby...
  4. It should also be noted that Conway's Game of Life uses the Moore neighborhoodWikipedia's W.svg rather than the von Neumann neighborhoodWikipedia's W.svg
  5. Geminoid Challenge
  6. LifeWiki:Replicator
  7. The scales of the ocellated lizard are surprisingly coordinated. Lizard grows into its flashy skin using a computer-like process by Emily Conover (6:00am, April 27, 2017) Science News.
  8. A living mesoscopic cellular automaton made of skin scales by Liana Manukyan et al. (2017) Nature 544(7649):173–179. doi:10.1038/nature22031.