Cellular automata is a term in computer science referring to a system in which automata interact with each other based on a set of simple rules, in a grid of cells. Each cell usually has a specific state (e.g. dead/alive, or a number from 1-10) which it continually updates based on the states of the cells around it.
An interesting feature of CA is that they are turing complete, meaning they are mathematically equivalent to a turing machine (a mathematical abstraction of a programmable computer), although a turing machine is not itself a cellular automaton. They are also very useful in modelling, and demonstrate principles of emergence: that a very simple system can produce immensely complex behaviour.
On this page, I'll explore two of the most famous examples of cellular automata: Boids and Conway's Game of Life
For a long time, scientists were fascinated by the ways in which birds flocked. Anyone who's seen a flock of starlings fly will know what I mean when I say that it seemed impossible for such small birds to be able to create such large patterns and change direction to avoid hazards so quickly and effectively. Because of this, for a long time it was thought that the birds had to be communicating in some way unbeknownst to us.
Enter Boids. In 1986, computer graphics expert Craig Reynolds created a simulation of many automata which move based on a small set of rules:
Each state iteration, each boid updates its velocity to:
This simple set of rules can create a very complex, unpredictable system which gives the appearance of birds flocking, despite no communication between the boids. In fact, the boids can form a swarm significantly larger than their visual radius, and flocks may split up and merge to avoid obstacles, making boids a classic example of emergent systems.
Boids are often used in films and video games to give the appearance of flocks of birds or schools of fish, and have been used in some other less obvious cases, such as programming Internet radio stations and optimisation problems.
It should be said that for these effects to look realistic, some parameters have to be fine tuned. However, this doesn't counteract the evidence for a lack of supernatural communication between flocking birds.
Conway's Game of Life is one of the most famous cellular automata. Created by mathematician John Conway in 1976, it plays out on a 2D grid of cells, each of which can be either dead or alive, usually represented by a boolean value true/false.
Like boids, the GoL is entirely deterministic and is defined by an initial state: which cells are alive, and which ones are dead. Each iteration, every cell counts the number of living cells adjacent to it (vertically, horizontally or diagonally) and updates its state based on the following criteria:
Similarly to boids, these simple rules can create incredibly complex patterns, with individual cells affecting the state of other cells far beyond their own direct sphere of influence. While both boids and the GoL are technically turing complete, this is much easier to see with the latter: a quick search online will show the endless possibilites of Conway's Game of Life, from fully functioning computers to even recreating itself. A lot more simpler are self-replicating and infinitely spreading patterns such as the one below.
As with boids, Conway's Game of Life does require significant initial fine tuning: a random initial state will almost always fizzle out into nothing. Another interesting feature of the GoL is that while it is easy to simulate an initial state and see what it leads to, it's virtually impossible to reconstruct an initial state based on a final state.
The Game of Life also falls into the category of zero player games, which refers to a game in which the only player's only role is to construct an initial state which will lead to a desired outcome.