Home
Syllabus
Assignments
Tests
Due: 8:00am, Thursday, May 6. Value: 30 pts. Submit to Sauron.
An elementary cellular automaton is a row
of cells, each of which has a state of either on
(1, drawn green)
or off
(0, drawn gray). Each cell can see only the cell to
its left, itself, and the cell to its right.
Since each of these three cells (left neighbor, itself, and right neighbor)
can only be on or off, at any time a cell will find itself in
one of eight possible situations, tabulated at right.
Over time, a cell will change its state.
For each time step, each cell looks at its left and right neighbors,
determines its situation (according to the table at right),
consults a rulebook
indicating what its new state should be for each possible situation,
and changes its state according to the rulebook.
Suppose, for example, that the rulebook is 01001000: Note that the 1's in the rulebook are at indices 1 and 4, saying that a cell should turn on in situations 1 or 4 and off in all other situations. Now suppose our automaton has fifteen cells, and it starts with the center cell on and the rest off.
Note that the center cell finds itself now in situation 2: its left neighbor is off, it is itself on, and its right neighbor is off. Overall, each cell finds itself in the situation as diagrammed below.
Now each cell consults the rulebook; the cell in situation 1, as well as the cell in situation 4, will discover that they should be on, while the other cells find they should be off. All cells change according, so the automaton now looks as below.
We can repeat this for the next two time steps.
If we draw eight time steps together, we get the following diagram.
This is essentially a small version of the Sierpinski gasket, a mathematical figure drawn at right. The Sierpinski gasket is more obvious when the figure is drawn for a larger cellular automaton (but still using rulebook 01001000).
I have written starting code for displaying
a cellular automaton and how it changes over time, which depends on
the Cell class that you are
to write. This starting code asks the user for a rulebook (which
should be given as a string of eight 0/1 values) and for the number
of cells, and then it draws a table giving the cell values as they
update over time.
Your assignment is to write the Cell class, which should have the
following constructor and methods.
Cell(init, rulebook)(Constructor) Constructs a new cell whose initial state is
init (which is either 0 or 1)
and who will use
rulebook to determine how to change its state.
The rulebook parameter will be a list of 0/1 values, where the number in index 0 corresponds to the proper new state when the cell is in situation 0 as in the table above.
get_state()Returns this cell's state, which should be 0 or 1.
step(left, right)Updates this cell's state, given its left neighbor's state
left (either 0 or 1)
and its right neighbor's state
right (also either 0 or 1).
After you get the program working, I recommend trying a larger number of cells, such as 63. Some interesting rulebooks to examine are: 01111000, 10110100, 01101100, 10010010, and 10010110.