# What are Cellular Automata?
Read on, or visit 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 & 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 as they went. (They were too busy telling each other old stories.) Here it is.
Before they tile the second row, Daedalus convinces Icarus to play a (very boring) game: when they place a tile, they always use the same color as the tile in the same position in the first row. When they finish the second row, it 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 "parent" tile—the one just above it. They tile some more rows, now following the new rule, and the second section of the wall makes a sort of 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 given the color of the "parent" tile above. 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 parent tile and the tile to the left of the parent tile. 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 for a given combination of neighboring parent tiles.
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, 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 boring 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.
They decide that it seems to be mostly random, except that 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.
# Finishing Touches
Put simply, a cellular automaton is a set of rules for deciding how to tile something (note that the cellular automaton is the set of rules, and not the final tiling itself). 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 than even the last "triangle" rule that Daedalus suggested. For example, cellular automata aren't limited to only two colors, and usually 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 & play with all sorts of cellular automata.