Cellular Automaton

Updated: Dec 1, 2020

Cellular automata are algorithmic models that use computation to iterate on very simple rules. In so doing, these very simple rules can create complex emergent phenomena through the interaction between agents as they evolve over time. To illustrate the functioning of a cellular automaton, we will take an example from probably the most famous algorithm called the Game Of Life devised by the mathematician John Conway. The Game Of Life is played on a grid of square cells. A cell can be alive or dead. A live cell is shown by putting a mark on its square. A dead cell is shown by leaving the square empty, each cell in the grid has a neighborhood consisting of all adjacent cells to it and there are just three rules governing the behavior of an agent. 1. Any live cell with fewer than two live neighbors dies; as if caused by under-population. 2. Any live cell with two or three live neighbors lives on to the next generation. 3. Any live cell with more than three live neighbors dies, as if by overcrowding. 4. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.[1]

Types Of Patterns

Cellular automata rule sets may be classified according to the degree of complexity that they can produce with Stephen Wolfram’s classification being the first attempt to classify the rules themselves in order of complexity.[2] The most simple pattern is called still life. Its product is probably the most simple class of pattern, called class one, where nearly all of these patterns evolve quickly into a stable, homogeneous state and any randomness in the initial pattern disappears. The second class of pattern we may get is where the system evolves into an oscillating structure. The simplest of these being a blinker that has a period two oscillation. We can also have oscillating structures that cycle over prolonged periods of time. For example, a pulsar has a period three oscillation, but oscillators of many more periods are known to exist. Class three patterns are random, where nearly all initial patterns evolve in a semi-random or chaotic manner. Any stable structures that appear are quickly destroyed by the surrounding noise. Local changes to the initial pattern tend to spread indefinitely. Here we can get what are called gliders where a group of cells appears to glide across the screen. This is a good example of emergence as we no longer see the simple rules that are producing them but instead this emergent structure of an object gliding. Lastly, automata can also produce patterns that become complex and endure over a prolonged period of time, with stable local structures. With these more complex patterns, cellular automata can simulate a variety of real-world systems, including biological and chemical ones.

Universal Computation

Since the advent of the Game of Life, new similar cellular automata have been developed that can do all sorts of things, such as create fractal patterns, that is, self-similar structures that repeat themselves over various scales of magnitude. Other games create patterns that can reproduce themselves. We might ask, is there anything that these automata can not do? From the perspective of computation, the Game Of Life can do anything that a computer can do. It can count to 100, calculate the volume of a cylinder, or if you wanted to figure out the cube root of 1230 you could encode this into a set of cells on the automaton and have it compute the value. The Game Of Life as simple as it is has been proven by computer scientists to be capable of universal computation.[3]

Computational Models

Cellular automata represent a new approach to mathematical modeling based upon computation. Von Neumann and Ulam originally introduced the concept in the mid-20th century, and then a few decades later the popular Game of Life brought interest to the subject beyond academia. In the 80s, Stephen Wolfram engaged in a systematic study of cellular automata after which he published a book called “A New Kind of Science” claiming that cellular automata could enable a new approach based upon the exploration of these algorithms.[4] One assumption within modern science is that simple rules can only create simple phenomena, and thus inversely complex phenomena must be the product of complex rules. The advent of chaos theory during the past few decades revealed this to be an invalid assumption as simple systems like a double pendulum proved to be capable of generating complex and chaotic behavior.[5] It is now increasingly accepted that complexity may not be the product of complex rules, but in fact, emerge out of the interaction of simple rules as they evolve over time. Cellular automata are the tools that capture and embody this paradigm within science.

1. Wikiwand. (2020). Conway’s Game of Life | Wikiwand. [online] Available at: https://www.wikiwand.com/en/Conway%27s_Game_of_Life [Accessed 1 Dec. 2020].

2. Wikiwand. (2020). Cellular automaton | Wikiwand. [online] Available at: https://www.wikiwand.com/en/Cellular_automaton#/Classification [Accessed 1 Dec. 2020].

3. Berto, F. and Tagliabue, J. (2012). Cellular Automata (Stanford Encyclopedia of Philosophy). [online] Stanford.edu. Available at: https://plato.stanford.edu/entries/cellular-automata/ [Accessed 1 Dec. 2020].

4. Wolfram, S. (2002). A new kind of science. [online] Champaign, Il: Wolfram Media. Available at: https://www.wolframscience.com/nks/ [Accessed 1 Dec. 2020].

5. Akerlof, C. (2012). The Chaotic Motion of a Double Pendulum. [online] Available at: http://instructor.physics.lsa.umich.edu/adv-labs/Chaotic%20Double%20Pendulum/Pendulum_2012_09_26.pdf.

Systems Innovation

  • LinkedIn
  • YouTube
  • Twitter
  • Facebook