A finite automaton is a device that can be in any of a finite number of states, like a multi-position switch, and is programmed to change from one of these states to another at regular intervals in response to the inputs it receives. The state that it will enter is completely determined by the state it is currently in and the inputs it is currently sensing.
A cellular automaton is a finite automaton that takes, as its inputs, the current state of other identically programmed automata. We can think of a collection of finite automata making up a linear sequence in which each automaton responds to the states of other automata that are nearby in the sequence.
The project today involves a program that simulates the operation of such a sequence of cellular automata and creates a graphical display showing the states that they assume as they run.
Because the current version of Chez Scheme does not come with a graphics library, we'll be using a much slower but better-equipped implementation of Scheme for this project: DrScheme, created by the Programming Languages Team at Rice University.
DrScheme provides its own XEmacs-like editor and interaction windows, so don't bother to start up XEmacs for this project.
The file automata-project.ss contains a Scheme program that simulates a sequence of cellular automata. Copy this file into your home directory.
Start up DrScheme and load the program into it by giving the shell command
drscheme automata-project.ss &
in the dtterm window. (Notice the ampersand at the end of this command.) It will take about a minute for DrScheme to load fully.
(When you're ready to exit from DrScheme, incidentally, you do so by
selecting Quit from the menu that appears when you click on
the word File at the left end of the menu bar at the top of
the DrScheme window.)
Experiment with editing the file that is displayed. Add your name to the opening comment and adjust the revision date.
Read the source code in the DrScheme window until you feel that you have a
good idea of what the program is supposed to do. Then click on the
Execute button at the top of the DrScheme window. This
directs DrScheme to run the program that it is displaying.
At this point, DrScheme will divide the window into an editing subwindow (at the top) and an interaction subwindow (at the bottom). This is similar to what happens when you run Chez Scheme under XEmacs, although the relative positions of the two subwindows are reversed.
DrScheme will begin to execute the program and to display the results, but because there is at least one bug in the program it will encounter an error at a fairly early stage. Helpfully, DrScheme draws a box in the editing subwindow around the expression that was being evaluated when the error occurred. Study the context of the error and the advisory message that appears (in red) in the interaction window. Determine the cause of the error.
Returning to DrScheme's editing subwindow, locate and correct the bug. When
you're ready to try the program again, press the Execute
button once more to start the program running. It is also possible to type
Scheme expressions into the interaction subwindow; pressing the
Enter key when the cursor is at the end of such an expression
causes DrScheme to evaluate it.
Once you have successfully executed the program, press the
Save button at the top of the DrScheme window to save the
revised version.
Revise the program so that the simulator starts all the automata in state 0
except the one in the middle, which is in state 1, and program each
automaton to use the modulo rule mentioned in the source code.
Revise the program so that there are only sixty-four automata in the sequence, but they run for one hundred cycles instead of only fifty.
Revise the program so that the automata can take on seven states instead of only five; let state 5 be represented by a black square and state 6 by a gray one.
Invent your own initial states and rule procedures and invoke the simulator to operate with them.
Revise the program so that the automata form a loop, with the first automaton being one of the neighbors of the last one. Consider how to modify the graphical display to exhibit this loop structure most effectively.
If you want to experiment with DrScheme, or simply want to find out more about graphics programming in Scheme, look at the on-line users' guide, ``PLT DrScheme: Programming Environment Manual''.
This document is available on the World Wide Web as
http://www.math.grin.edu/~stone/courses/scheme/automata-project.html
created April 22, 1998
last revised June 21, 1998