Cellular automaton

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

Part of a
convergent series on
Mathematics
1+1=11
v - t - e

Relationship to evolution
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

Conway's Game of Life, developed by British mathematician John Horton Conway in 1970, 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:[3]

  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.[4]

In other words, unlike in other cellular automata, cells in Conway's Game of Life have only two states, alive and dead.[5] In spite of this, many complex patterns have been found or engineered 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. [6] A small replicator based on a different mechanism has been found in HighLife, one of the variants of Conway's Game of Life where the rules above are altered.[7] Conway's Game of Life is also capable of creating a universal computer [8], a universal constructor, or even a fully functioning simulation of itself.[9]

Life imitates "Life"

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.[10][11]

<iframe src='//www.youtube.com/embed/Usr_jGAt8BY?' width='300' height='169' frameborder='0' allowfullscreen='true'></iframe>
gollark: The last thing in a lambda is what gets returned, right?
gollark: I don't *think* so.
gollark: **Meta**gollariosity.
gollark: ```Error: (=) bad argument type - not a number: #<unspecified> Call history: <eval> [grudger] (memq 1 x) <eval> [helper] (y moves-y moves-x x) <eval> [metagollariosity] (z y x z) <eval> [maybe-tit-for-tat-or-grudger] (= (pseudo-random-integer 2) 1) <eval> [maybe-tit-for-tat-or-grudger] (pseudo-random-integer 2) <eval> [maybe-tit-for-tat-or-grudger] (grudger x y z) <eval> [grudger] (memq 1 x) <eval> [helper] (cons (cadr current-moves) moves-x) <eval> [helper] (cadr current-moves) <eval> [helper] (cons (car current-moves) moves-y) <eval> [helper] (car current-moves) <eval> [helper] (map + scores (prisond (car current-moves) (cadr current-moves))) <eval> [helper] (prisond (car current-moves) (cadr current-moves)) <eval> [helper] (car current-moves) <eval> [helper] (cadr current-moves) <eval> [prisond] (= x y) <--```???
gollark: I'm trying to make all gollarious, but this is hard.

See also
  • 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
  1. An animation of evoloops evolving
  2. Evoloop abiogenesis
  3. http://web.stanford.edu/~cdebs/GameOfLife/
  4. Because we all know it takes three people to form a babby...
  5. It should also be noted that Conway's Game of Life uses the Moore neighborhoodFile:Wikipedia's W.svg rather than the von Neumann neighborhoodFile:Wikipedia's W.svg
  7. LifeWiki:Replicator
  8. http://www.conwaylife.com/wiki/Universal_computer
  9. http://www.conwaylife.com/wiki/Unit_cell
  10. 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.
  11. A living mesoscopic cellular automaton made of skin scales by Liana Manukyan et al. (2017) Nature 544(7649):173–179. doi:10.1038/nature22031.
This article is issued from Rationalwiki. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.