These notes are meant to summarize, record and lead our investigations into cellular automata, as part of the Young Scholars Program, conducted over June and July 2003.
A cellular automaton can be thought of as a sort of simple game, with playing pieces and rules; or as an ideal computer with data and a program; or (maybe) as a chunk of the real world, like a set of gas particles in a container, that move, bounce, and collide with each other.
Cellular automata are in some sense about as simple a system as you can imagine, and yet some of them seem able to exhibit a surprising amount of complexity. Even with very basic rules, it seems that sometimes you can't predict whether a glorious pattern or random static or a solid black screen will emerge.
Two suggested articles to read now:
We will think of a cellular automaton as a collection of "cells" having four important features:
In the examples that we will begin with, the geometry is an infinite line. Each cell communicates only with its left and right neighbor, and has only two states, 0 and 1. This means that there are 256 possible different rules, because there are 8 different possible sets of states for the cell and its two neighbors, and we have two choices for the result of each state.
One piece of the rule would tell you that if the cell and its left and right neighbor were in the states "1", "1" and "0", then the next state for the cell would be "1". We could symbolize this part of the rule as:
110
1
The rule for a particular cellular automaton requires specifying what happens
in all 8 possibilities. Thus, a sample rule might read:
111 110 101 100 011 010 001 000
0 1 0 1 1 0 1 0
This happens to be the rule called "Rule 90", because if you read the
results line as a binary number, "01011010" you have a decimal value of 90.
In fact, if you think about it, this means that there are 256 possible
rules numbered 0 through 255, and that rules 0 and 255 are especially boring
(everything turns white or everything turns black).
Once we have a "universe" and a set of rules for how it can change, we need to have a particular example to work on. We imagine that time ticks ahead in seconds, that we start at second 0, and update the cell values each second. Since we're doing a one dimensional problem, it's convenient to write the new values on a line just below the old ones, so we don't lose the old results. In order to get started, we put any old values we like onto the first line, but for convenience, we usually put a single black square in the middle. This makes our work easier because usually the rules are set up so that the strings of white squares on either side stay "mostly" white, so we only have to concentrate on the black square, and its immediate neighborhood.
For instance, here's what a few steps of rule 90 might look like, assuming that time flows from top to bottom in the picture:
0 0 0 0 1 0 0 0 0 <-- Time = 0
0 0 0 1 0 1 0 0 0 1
0 0 1 0 0 0 1 0 0 2
0 1 0 1 0 1 0 1 0 3
1 0 0 0 0 0 0 0 1 4
Notice that now we've hit the boundary of the region, and we have to
decide whether we want to add more columns of 0's to our picture because
we were working in an infinite line, or we're going to wrap around, or
make up some rule for handling the boundary cells specially.
As an exercise, set up on graph paper "an initial condition" involving a single black cell, and see what happens over four or five steps as you apply rule 30, 90, 110 or 250 repeatedly. This clearly takes a lot of work and paper, and it would require more patience than we have to take this out to 100 lines. But it's often only after hundreds of lines that you start to see the really interesting patterns!
Use a browser to find, download, and install MCell and Life32.
Right now, you can't seem to install either program into "Program Files"; installing them in your "My Documents" area works, but then the programs fail when you run them, with an error caused by trying to access the OLE Registry. I'll try to find out what's wrong there.
In the meantime, however, you can actually double click on the help file for MCell. One of the topics covered is "1D binary cellular automata", so you can see how that program wants you to set up the rule and run a simulation. Try reading through that information, so you'll be ready to run some rules when we get the program running.
In one of the articles we read, there was an intriguing statement that the cellular automaton rule 30 seemed to generate "random" data. Starting with a single black cell in the first row, a picture of the evolution of a rule 30 automaton certainly looks complicated, but to say it is random is to say that there seems to be no simple relationship that can summarize the pattern. Steven Wolfram says that some data from rule 30 is used as the random number generator in the Mathematica program.
Our goal, then, is to try to set up a simple program in Visual Basic that can produce successive rows of a row 30 cellular automaton. Our best guess is that, if we start out with one black cell in the center, the state of that cell from step to step is a random variable. So we'll save just that one bit from each step, and see if we can analyze the sequence of bits for randomness.
We talked for a while about how to set up such a program. What sort of values would the data have, logical, integers, characters? How would the successive steps of the cellular automaton be stored? We decided to save just the current row and the next one, although it seems if you really were pressed for storage, you only need one row, and a few temporary variables. How do you implement the rule? We figured out a simple but wordy way, and then a quick way using nested IF statements. Then we looked at a way to turn such a logical formula into a mathematical formula; we decided to stick with the logical IF statements, because it was easier to work with.
Once we get the program running, there are several things to think about, including graphical display, writing the bits to a file, and figuring out how to test whether the data is random.
Another issue was to start gathering bit map (BMP) files, and make sure that we could convert them to PNG files suitable for the creation of a poster at the end. We took a sample BMP file, opened it with the GNU Image Manipulation Program (GIMP), and saved it as a PNG file:
The transformation seemed to work fine, so we should be set for the poster!