Cellular automaton

Part of a convergent series on Mathematics

1+1=11

Pyramid Innumeracy Fermat Primes No Free Lunch Theorems Statistics Ramsey theory Millennium Prize Problems Proof of the inconsistency of arithmetic

We are number one

Hypatia of Alexandria Darrell Huff Tom Lehrer René Descartes v - t - e

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]

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 10¹⁰ 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 "Gosper glider gun" in the Game of Life: an example of simple rules producing "gliders" ad infinitum

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

See also[edit]

• Abiogenesis
• Emergence
• Red Lynx

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]