# What are Cellular Automata?
Read on, or skip straight to the emulator.
# Icarus and Daedalus Tile a Wall
Icarus and Daedalus have been hired to tile a wall with square tiles. The tiles come in two colors: black and white. The clients want the wall to be tiled in a grid one row at a time, starting at the top. The clients oddly don't care how the black and white tiles are arranged in the grid.
Icarus and Daedalus begin tiling. The first row ends up looking pretty random, since they didn't pay much attention to which colors they were using. (They were too busy telling each other old stories.) Here it is.
Before they tile the second row, Daedalus convinces Icarus to follow a (very simple) rule: when picking a tile for a position, use a tile of the same color as the tile above that position. When they finish the second row, the wall looks like this.
They do some more rows like this: when they lay down a tile, they make sure it's the same color as the tile just above it.
Icarus gets bored with the simple striping pattern this creates and wants to change the rule, just a little. He decides that when they lay down a tile, they'll make it the opposite of the one just above it. They tile some more rows, now following the new rule, and the second section of the wall makes an almost checkered pattern.
Daedalus describes this "almost-checkered" rule with two pictures: one with a black tile above and a white tile underneath, and another with a white tile above and a black tile underneath. Each picture shows them which color to use in a position given the color of the tile above that position. Daedalus calls these pictures the "transition rules" for their tiling game.
Icarus points out that both patterns have been pretty repetitive. When deciding on a new tile's color, they've only been considering the color of the tile right above it. He suggests that the patterns could be more interesting if they considered two tiles: the tile directly above and the tile to the left of that. Daedalus agrees and suggests a new rule: if the two tiles above are the same color use black, and if they're different use white.
This new rule is more complicated than the others, so Icarus asks Daedalus to draw another picture of the "transition rules," like before. This time they draw four pictures. Each one shows which color tile to use in a position for a given combination of neighboring tiles above that position.
Icarus is doubtful that the new pattern will be interesting; after all, it's just a combination of the "striped" and "almost-checkered" rules they were using before: use the "stripes" rule if the left tile is black, and use the "almost-checkered" rule if the left tile is white. But he goes along with Daedalus's idea.
Starting off with the last row from the "almost-checkered" section of the wall, they add a new row following the new rule.
It takes a little while for them to get used to this new rule, and they have to look at the drawing they made to remember what color tile to use, but it's definitely not as simple as the other two rules. Icarus and Daedalus decide to tile several more rows following this rule, to see if it makes some kind of larger pattern.
It seems to be mostly random, and it sometimes makes black triangles.
The wall is now fully tiled. Here's how it turned out.
It probably won't win any artistic prizes, but Icarus and Daedalus have used cellular automata to tile the wall. Each "rule" that they came up with was a different cellular automaton.
# Conclusion
A cellular automaton is a set of rules for deciding how to tile something, given some previous "generation" of tiles. That something can be a wall, or an infinite plane, or the surface of a sphere, or almost any surface you can think of.
The rules can be very simple, like the "striped" and "almost-checkered" rules, and can get more complicated. For example, cellular automata aren't limited to only two colors, and often use numbers in place of colors.
You can view the rules from this story in the emulator on this site.
The cellular automata drawn in this story and at the emulator are all drawn row-by-row, to make a single grid of cells. Many other cellular automata start with a full grid, and then have rules for drawing a new grid. By drawing many new grids over and over, they can make simple animations. The most well-known cellular automaton, Conway's Game of Life, works like this.
Here are some other nice resources to learn about or play with cellular automata.
- Wikipedia for more info and a deep rabbit-hole of related articles.
- Wolfram MathWorld for lots of numbers and graphs.
- Golly, a program you can run locally to make and play with all sorts of cellular automata.