## Cellular Automata

Cellular automata are simulations on a linear, square, or cubic grid on which each cell can be in a single state, often just ON and OFF, and where each cell operates on its own, taking the states of its neighbors as input and showing a state as output.

One of the simplest examples of these would be a 1-dimensional cellular automaton in which each cell has two states, ON and OFF, which are represented by black and white, and where each cell turns on if at least one of its neighbors are in the ON state. When started from 1 cell, this simply creates a widening black line. When the layers are shown all at once, though, you can see that it makes a pyramidal shape.

For example, in the figure above, the second line is generated from doing the rule for all cells in the first line, the third line from the second line, and so on. More complicated figures can be generated from different rules, such as a cellular automaton in which a cell changes to ON if either the cell to it’s top left or top-right is ON, but not if both are on. This creates a Sierpinski Triangle when starting from a single cell:

Stephen Wolfram developed a numbering system for all cellular automata which base only on themselves, their left-hand neighbor, and their right-hand neighbor, often called the elementary cellular automata, which looks something like this for the Sierpinski Triangle automata (Rule 18):

This code has all possible ON and OFF states for three cells on the top, and the effect that it creates on the cell below them on the bottom. Using this system, we can find that there are 256 different elementary cellular automata. We can also easily create a number for each automaton by simply converting the ON and OFF states at the bottom to 1s and 0s, and then combining them to make a binary number (00010010 in the Sierpinski Triangle example). Then, we convert the binary to decimal and so get the rule number. (128*0+64*0+32*0+16*1+8*0+4*0+2*1+1*0= 18 for the example). We can also do the reverse to get a cellular automata from a number. Using this method, we can create pictures of all 255 elementary cellular automata:

Some of these are rather interesting, such as Rule 30 and Rule 110:

Whilst some are rather boring, such as Rule 0, which is just white, or Rule 14, which is a single diagonal line.

There are many variations on this basic cellular automata type, such as an extension of the code where next-nearest neighbors are also included. This results in 4294967296 different cellular automata, a few of which appear to create almost 3-dimensional patterns such as the 3D Tetrahedrons cellular automata (rule 3283936144 ) which appears to show certain tetrahedral-ish shapes popping out of a plane.

There are also totalistic cellular automata, which are created by basing the next cell somehow on the average of the top-left, center, and top-right cells above it. These can have more than two states, and sometimes produce very strange-looking patterns, such as Rule 1599, a 3-state cellular automata:

As well as all these, there are continuous-valued cellular automata, which, instead of having cells that can only be in certain states, have the cells have real-number values. Then, at every step a function is applied to the cell that is to be changed as well as it’s neighbors. A good example of this is the Heat cellular automaton, in which the function is ((left_neighbor+old_cell+right_neighbor)/3+ a number between 0 and 1) mod 1). It produces a “boiling” effect, in which it resembles a pot of water slowly boiling on an oven.

There are tons more 1-dimensional cellular automata; Stephen Wolfram filled most of an entire (1200 page) book with these. However, there are essentially only 4 classes of cellular automata. The first type is the most boring; it is where the cellular automata evolves into a single, uniform state. An example of this would be the Rule 254 elementary cellular automata (the first example), which eventually evolves into all black. The second type, repetition, is a little more interesting, as it does not evolve into a single state but is instead repetitive. This can include a single line, simple oscillation, or fractal-like behavior, an example of which would be Rule 18. The third type is simply completely chaotic behavior- not very interesting, but definitely more than the previous two- such as in Rule 30. The last type, type 4, is where there are many individual structures that interact, sometimes passing right through, other times blowing up. An example of this would be Rule 110. This type is probably the most interesting to watch, as the eventual outcome is unknown.

These 4 types cover nearly any cellular automata, except for the ones which appear to be midway in between the types.

We can easily go past 1-dimension and study two-dimensional cellular automata. Probably the most famous of these is Conway’s Game of Life, invented by John Conway in 1970. In it, clusters of cells appear to grow, and then collapse as “gliders” move across the screen. It only uses 4 rules, and easily falls into the category of Class 4 cellular automata.

The rules are:

1. Any live cell with less than 2 neighbors dies. (starvation)

2. Any live cell with more than 3 neighbors dies. (overcrowding)

3. Any live cell with 2 or 3 neighbors stays alive.

4. Any dead cell with three live neighbors becomes alive (birth)

Here, the neighborhood of a cell is defined as the 8 cells that surround it.

When the Game of Life was first shown, tons of people went crazy writing programs for simulating it on computers, and supposedly thousands of hours of computer time were “wasted” simulating these patterns. One worker at a company even installed a “Boss” button for switching the display from Life to whatever he was supposed to be working on when his boss walked by! Conway had offered a $50 dollar prize to whoever could find a pattern that expands infinitely. This could be a sort of glider gun, which shoots out gliders, a puffer, that leaves a trail of debris, or a spacefiller which expands out in all directions. The prize was claimed by Bill Gosper when he discovered the Gosper Glider Gun.

Since then, lots of new patterns have been discovered in the Game of Life, such as a puffer train, a hexadecimal counter, a fractal-generator, and even a “computer” which will do practically anything it is programmed to do.

There are many other 2-dimensional cellular automata, which can be written in a certain notation which tells with which neighbor-numbers the dead cell turns alive, and for what neighbor-numbers the live cell stays alive. For example, Conway’s Game of Life could be written as B3/S23 . Many other cellular automata can be written using this notation. Some of the more interesting ones are Fredkin’s automaton (B1357/S02468) , which replicates any starting pattern. That’s all it does, no exceptions, so there’s no possibility of making anything like an adder in it. Another interesting one is the “Maze” rule (B3/S12345) , which produces maze-like patterns. Changing the rule to B37/S12345 creates dots that move through the shape. One of the most interesting of these, though, is 2×2 Life (B36/S125) , a rule that is similar in character to Life but has much different patterns. Gliders are also a bit more rare, although there are a lot of interesting oscillators. In rules like these, such as Day & Night (B3678/S3478) it makes almost no difference whether the colors are reversed. Day & Night also, at the end of patterns, has lots of oscillators.

Naturally, you can extend this form to allow multiple states. Brian’s Brain (/2/3) is an example of this, in which there are three states, and in which gliders and glider guns are very much common. In fact, Still Lifes are almost nonexistent! The notation above means that a cell in state 1 (and only in state 1) stays alive if it has (null) neighbors, that a dead cell becomes a state 1 cell if it has 2 neighbors, and that there are 3 states (0,1,2) .

There are many modifications of this rule, one which causes scaffold-like structures to form, and even one which combines with Conway’s Game of Life!

You can easily make your own rules by simply choosing numbers to put in. Many of them appear to just be chaotic, but you can find rules which create rather interesting patterns. A good one is the Star Wars cellular automaton, 345/2/4 , which starts out like the Brian’s Brain rule but soon creates structures which shoot out gliders. A fun thing to do in this rule is to make “Train tracks” which let 1×3 rectangles move around them in both directions. Of course, you can also simulate all of the Life-ish rules by changing the number of states to be 2, so that there are only ON and OFF states.

As if all this weren’t enough, there’s even a generalization of the previous into arbitrarily many rules for arbitrarily many states, as a rule table. Basically, the rules are based on a large table that tells the cell in a certain state to change to a different (or the same) state if it has <this> many live neighbors. The different rules for each state makes it easy to get the cellular automaton to do exactly what you want it to do. A good example of this type of rule is the Wireworld cellular automaton, invented by Brian Silverman, in which electrons travel down wires simulating the connections in a computer. It’s easy to make a 1-way gate, an AND gate, a clock, a NOT gate… and nearly everything you’d need to create a computer. In fact, Mark Owen even made a wireworld computer that calculates and displays the prime numbers!

Rudy Rucker has also made a lot of Rule Table cellular automata, one of the most interesting being his Cars cellular automaton, which produces racing cars in several types, not usually something you’d expect to see from a cellular automaton. The cars also crash into each other, and, in the process, make rather strange cars.

I have also made an interesting cellular automaton, which only uses 2 states, but still shows interesting behavior on wrapped grids, called SkyscraperMakers. In it, large structures are easily made, and there is a very simple puffer which requires only 6 cells. Signals also appear to transfer through the structures, but mostly just lower the towers.

There are also cellular automaton rules where only 1 cell is actually active at any one time. An example of this is the Langton’s Ant cellular automaton, in which the moving cell has two rules:

1. If you are on a white square, turn right, flip the color of the square from white to black, and move forward one square.

2. If you are on a black square, turn left, flip the color of the square from black to white, and move forward one square.

Although this seems very simple, when the cellular automaton runs on a blank grid the pattern produced is rather chaotic. In fact, you have to wait around 11,000 steps until the “ant” produces a “highway” in which the ant repeats the same pattern over and over.

Naturally, there’s a generalization to multiple states and different rules, in which you simply tell the ant what to do when it touches a certain state. It is usually expressed using a string of Rs and Ls to show what direction the ant takes when it touches a certain-colored cell. For example, the classic Langton’s Ant rule could be expressed as RL, meaning that it turns right when it touches a cell of state 0 (white), and turns left when it touches a cell of state 1. Using this generalization, there are some rather interesting cellular automata. For example, LLRR makes a cardiod shape:

Whilst one of the longer rules, LRRRRRLLR fills space around itself in a square.

Naturally, the infinity of 1-dimensional and 2-dimensional cellular automata wasn’t enough for some people, who proceeded on to 3-dimensional cellular automata. The notation for these is similar to the normal Life notation (i.e., B (something)/S (something)), except that the numbers go from 0 to 26 instead of from 0 to 8. There are some interesting analogs of 2d cellular automata, such as Brian’s Brain, which have been discovered (B4/S) :

As well as some new rules, such as the “Clouds” rule (B13,14,17,18,19 /S13,14,15,16,17,18,19,20,21,22,23,24) in which random patterns quickly form cloud-like blobs and bridges between the blobs. The “clouds” eventually shrink down, sometimes to nothing but sometimes forming rather simple oscillators:

There has even been a version of Life in 3D, however, it turns to simple oscillators very quickly. Supposedly, gliders can be formed, but I haven’t seen any.

The problem with 3D cellular automata, though, is that computer screens are 2-dimensional. When a computer screen displays a picture of a 3D cellular automata, the front (that we see) may be rather dull, while the other side may be very chaotic, but we wouldn’t know the difference. Also, there may be lots of action inside a blob, but we can’t see what is happening inside.

An interesting way to make a 3-dimensional shape out of a cellular automata is to simply stack all the stages of a 2-dimensional cellular automata on top of each other. This makes the cellular automaton seem quite a bit different. Patterns like the Gosper Glider Gun in Conway’s Game of Life turn into a tower with suspension cables on one side, Langton’s Ant into a Sears Tower-like skyscraper, and Brian’s Brain I don’t even want to think about. It’s rather fun to construct these out of blocks (specifically ones that can be joined together) , as the results are often surprising.

Part of Wolfram’s book was devoted to designing and finding certain cellular automata that can do *anything*– calculate what 2+2 is, emulate other cellular automata- even display letters- called Universal cellular automata. The simplest of these to show universal would be Conway’s Game of Life, by making AND gates, OR gates, a memory cell, a 90 degree reflector ,and a NOT gate. Many of these base on bashing gliders together to form certain outcomes, and the NOT gate is the hard one- it needs to use a glider gun, or something to send out gliders, in order to actually be a NOT gate. Once that’s made, the rest is simple.

A similar method can be used to show that WireWorld is universal- by making the necessary logic components, various computers can easily be made, such as Mark Owen’s massive prime calculator. There are even constructions made by putting logic gates together such that 1-dimensional cellular automata can be made!

Von Neumann also designed a 2-dimensional cellular automata, the sole purpose of which was to show that computers were possible in cellular automata. The rules are quite complex, mostly operate on signals passing through wires and writing cells, and the cellular automaton has a whopping 29 states. Replicators are possible, but they use humongous “tapes” to store how the structure should be built.

Now here’s the amazing part: Even 1-dimensional cellular automata can be universal. In particular, Wolfram showed a certain 19-state next-nearest neighbor cellular automaton which, given the right setup, will emulate any other 1-dimensional cellular automata on a huge basis (20 cells per cell). Some examples of it emulating cellular automata are below:

In particular, although it is hard to see, the 19-state cellular automaton is emulating rule 90 and rule 30, respectively.

Most amazing, though is that, though it is anything but straightforward to prove, Rule 110 is a universal cellular automaton. This was done by showing how it could emulate another 1-dimensional cellular automata class, the cyclic tag system, and working from there. Eventually, Wolfram shows it emulating other elementary cellular automata, computing, and even emulating Turing machines.

Quite a lot of cellular automata programs exist (many of them are listed at http://cafaq.com/soft/index.php), so I’ll simply list some of the best ones that I have found.

One of my favorite programs is Mirek’s Cellebration (MCell), made by Mirek Wojtowicz, which has quite a lot of cellular automata rules (200+), and even more cellular automata patterns. It has a large Life pattern database, as well as allows you to make your own rules and save them easily. Probably the only problems with this are that the speed of the automaton may vary depending on the number of life cells on the board, and that the software is no longer developed. However, you can add on small extensions and even change the source code of the online Java version. You can either download it here, or see the Java implementation.

Another program for simulating cellular automata is Five Cellular Automata, which simulates exactly 5 types of cellular automata: A small generalization of Life, using 4 parameters and q states; The Belousov-Zhabotinsky reaction, as a cellular automaton; a cellular automata in which blobs of colors try to meet with each other, and eventually take over the board; a probabilistic cellular automaton in which “viruses” break out among the population, kill everybody, and eventually die as the population regrows; and lastly, a DLA model. The program simulates all 5 rather well, but it only does those 5, and there are no manual editing features. This makes it so that the program is good for watching, but not useful for any experimentation. You can download it at the Hermetic Systems website.

The best of these which is being developed on would easily be Golly, a cellular automata program that has infinite universes, uses Bill Gosper’s speedy Hashlife algorithm, has hundreds of patterns, including a few Life lexicons, and even is scriptable (with examples!) in both Python and Perl. And it reads practically every CA file ever made. The only problem is that completely new rules, such as making a rule table cellular automaton, isn’t very easy unless it’s a Life-like cellular automaton (B something/S something). You can download it at the project’s Sourceforge page.

Lastly, there’s CAPOW by Rudy Rucker, which is a program for generating continuous-valued cellular automata. It supports 1D and 2D rules, as well as a number of discrete-valued cellular automata. It also has a mode in which the 2D cellular automata is extruded, based on what state the cell is at, into a 3D grid. It has quite a lot of cellular automata, can make up new ones, and includes a screensaver which shows various cellular automata animating. The only bad part is that it’s a bit confusing to make different rules or make new CA classes. You can download it at Rudy Rucker’s website.

There are tons more cellular automata that have not been studied, so the field of Cellular Automata is still an interesting field to explore in and find new and interesting rules.

Another great post Neil – thanks.

You don’t seem to have written about the Sunday at G4G9 yet, is that coming?

Thanks for yet more interesting things to think about.

Colin.

The very next blog post that I do is going to be about Sunday at G4G9, so I’m currently working on it.

Also, I actually had to leave out a bunch of cellular automata types, such as the Archean cellular automata, or the Gardens of Edens in Life, because I didn’t want the blog post to be as big as Wolfram’s book!

Oh, I can understand that. There is a lot to write about with CA’s, I’m pretty sure even Stephen’s book isn’t complete. I still occasionally give proofs that Life is Turing equivalent, and it’s fun constructing things in Wire World.

BTW, I know Mark Owen. I must point him at your site when I get the chance.

Cheers!

PS: Incredibly sad news about Martin.

Cool stuff – gotta love fractals!

Hi Nick,

Would you mind making the black background you have at the sides a lighter color? Or make the print whiter and bigger? It’s just very hard to read if you’re in a light room, which, as it happens, I am, because my planet is currently tilted towards my local star.

I think you should add a self-photo too.

Good content, though. I can’t believe how much time you must spend on this thing.

Good work,

Mark.

This is really good and better understandable for everyone.

can somebody give me the code or links for Langton’s Virtual Ant program that is shown above.

Thanks,

Sara

Brilliant article.

Over the past few years (on and off), I have concentrated my efforts in creating 1D binary (rule 2) patterns. Some can be seen here… http://the-orangery.weebly.com/ca.html

Here’s a little page where you can experiment with the simple cellular automata from Wolfram’s book: http://hughw.net/ca/index.html