• Contribute
• What's New
• Submit News

This article will present several well-known, simple cellular automata along with example Java applets. The cellular automata we will look at include Langton's Ants, Conway's Life, Conway's Self-replicated Loop, Wolfram's one-dimensional automata and Termites. All Java examples have been written (and are included) with the Generation5 JDK.

Wolfram 1D

Stephen Wolfram was one of the first people to extensively study cellular automata, especially simple the 1-dimensional CAs shown below. Wolfram CAs follow very simple rules depending on the automata above it. Rules are often best expressed in graphical terms. For example, below is a simple rule that shows how the next row is determined by the above three neighbours.

Rules can be encoded simply by using binary-numbering. For example, the above rule could be expressed 01111110 in binary, or 126 in decimal. Below is rule 126 displayed in both a timestep diagram started from a single point, and a full-size diagram of rule 126 iterated from a random initial state.

The Java applet displays four instances of Wolfram's 1D CA. The first instance is rule 126 started from a midpoint, and the second is rule 146 from a random initial state, as well as two examples of an extended neighbourhood CA.

Langton's Ants

Chris Langton created his ant cellular automaton to demonstrate how their simple properties lead to very complex shapes and structures. The ant follows three simple rules:

1. Move forward in the direction the ant is facing
2. If the ant lands on a black square, turn it white and turn right
3. If the ant lands on a white square, turn it black and turn left

The most interesting thing about Langton's ant is that it is time-reversible. Given any state, the system can be reversed to the initial state. Most CAs, such as Conway's Life, are time-irreversible - given any state, you cannot determine what state led to it.

Below you can see a timestep of two ants on a 500x500 world. You can see how they form clumps and 'highways' as they transverse the world.

Chris Langton is also well known for his self-replicating loop. The loop is non-trivial in implementation, with 8 states and 219 rules but demonstrates self-replicating cellular automata. The loops replicate in four directions, before closing themselves and becoming stable. The image below shows the loops across 600 timesteps:

Termites

Termites follow 3 simple rules:

• A termite moves in a random direction
• If it hits a woodchip and is not carrying a woodchip, it picks up the woodchip
• If it hits a woodchip and is already carrying a woodchip, it drops the woodchip

These rules would seemingly not cause any sort of behaviour, but in fact given enough iterations, these termites will form little piles. Below is a timestep diagram from 0 and 10,000 and 20,000 iterations. As you can see, the piles generally reach a certain size, then the termites start ferrying the same woodchips back and forth.

The applet implements the basic Termite rules with a few additional stipulations. The termites do not necessarily follow a random walk, instead they make a random 45-degree turn to either the left or the right upon every iteration. Furthermore, when the termite hits a woodchip, it makes a 180-degree turn.

Conway's Life

Conway's Life is probably the most famous example of cellular automata. Conway had wanted to find the simplest CA that supported universal computation. He decided to use two states, dead or alive, and four simple rules:

• If a live cell has less than two neighbours, it dies.
• If a live cell has more than three neighbours, it dies.
• If a dead cell has exactly three neighbours, it comes to life.
• Otherwise, all other cells remain in their original state.

Below is a simple timestep image, although it is rather hard to understand how Life works from a static image.

The demonstration applet is fairly extensive: featuring a random world and three shapes seen in Life.

WireWorld

WireWorld is a very interesting CA, because it remains a very simple CA but demonstrates universal computation very simply. WireWorld has only four states, that can be described thus:

• 0 - background.
• 1 - Electron head.
• 2 - Electron tail.
• 3 - Wire cell.

The rules are equally simple. Every step (1) an electron head becomes an electron tail, (2) an electron tail becomes a wire cell and (3) a wire cell will become an electron head if there are one or two other electron heads in the surrounding eight neighbours.

Despite the simple rules, it is very easy to demonstrate how this cellular automata can be configured to perform computations. Below are three arrangements showing OR, AND and XOR logic gates, along with the 4 possible inputs.

Large configurations of these logic gates can be strung together to produce computational elements (the same way modern digital computers work). Below is an image that shows a binary adder implemented in WireWorld. The first 8-bit number is inputted in the A7-A0 row, the second number in the B7-B0 row. After a few thousand iterations, the 16-bit result is displayed within the cyclic loops C0 through C15.

Conclusion

The cellular automata covered in this article only grazes the surface—slime mold simulations, traffic modelling, predator-prey behaviour, human migration studies and collision-based computing are just some of the areas CAs have been employed in research. If you would like to explore CAs further, you can utilize Generation5's JDK to create your own CAs.