Cellular Automata
Contents:
Cellular automata are described in:
-
Christopher G. Langton
"Life at the Edge of Chaos"
In: Christopher G. Langton, Charles Taylor, J. Doyne Farmer, Steen
Rasmussen (Editors)
Artificial Life II
Addison-Wesley, 1992, pp 41-91
A cellular automaton (CA) is a D-dimensional matrix, with
an identical finite state automaton (FSA) on each cell.
At consecutive time steps, all automata perform a transition to a new state.
The new state of an automaton is determined by a function on the old
states of the automaton and some of its neighbors.
A well known example is John Conway's Game of Life. This is a
2-dimensional CA, each FSA in one of two states (on or off), with a
neighborhood of 9 FSA's (including the current FSA in the middle).
Another example are 1-dimensional CA's. The automata are lined up next to
each other. A figure -- such as the example at the top of this document
-- is constructed by lining up consecutive states in time. Al automata
are placed on a horizontal line, two consecutive lines representing two
consecutive states of all automata. The leftmost cell is considered to
be the right neighbor of the right most cell: the line of automata forms
a closed loop. In the example, each automata can be in one of four
states, represented by the colors red, green, blue, and black. Each new
state of an automaton is determined by five values: the old states of
the automaton itself, two neighbors on the left, and two on the right.
Available software:
- ca.c
- Compiles on Unix (X11) or MS-DOS (VGA). Refer to the top of the page for
instructions.
- ca.exe
- MS-DOS executable.
The program implements the 1-dimensional, 4-state, 5-neighborhood
(current included) cellular automata, as described in Christopher
Langton's article. The CA is defined by 45=1024 values for
each possible input state. The program creates a table of 1024 values,
partly filled with 0 (transition to black), partly filled with random 1,
2, or 3 (transition to blue, green, or red) as defined by Langton's
lambda value. An input of all 0's results in output 0.
Because there are 1024 values defining the CA, each one of
four values, there are 41024 possible different CA's
(actually -3, because of restriction on all 0 rule), or
32 317 006 071 311 007 300 714 876 688 669 951 960 444 102 669 715 484
032 130 345 427 524 655 138 867 890 893 197 201 411 522 913 463 688 717
960 921 898 019 494 119 559 150 490 921 095 088 152 386 448 283 120 630
877 367 300 996 091 750 197 750 389 652 106 796 057 638 384 067 568 276
792 218 642 619 756 161 838 094 338 476 170 470 581 645 852 036 305 042
887 575 891 541 065 808 607 552 399 123 930 385 521 914 333 389 668 342
420 684 974 786 564 569 494 856 176 035 326 322 058 077 805 659 331 026
192 708 460 314 150 258 592 864 177 116 725 943 603 718 461 857 357 598
351 152 301 645 904 403 697 613 233 287 231 227 125 684 710 820 209 725
157 101 726 931 323 469 678 542 580 656 697 935 045 997 268 352 998 638
215 525 166 389 437 335 543 602 135 433 229 604 645 318 478 604 952 148
193 555 853 611 059 596 230 656 (-3).
The program can be run without options. For a list of valid option,
start the program with an invalid option ;-)
List of options
- -l value
- Lambda, a value between 0 and 1. When lambda is 0, each transition
will be a transition to state 0 (black), complete order. With lambda
1, each transition will be to state 1, 2, or 3 (blue, green, red),
complete chaos. Complex behavior occurs somewhere between order and
chaos. Lambda = .4 gives interesting results, .45 when used in
combination with the -i option.
- -i
- When constructing the transition table, Langton uses a restriction
he calls Spatial Isotropy. He writes: "All
planar rotations of a neighborhood state will map to the same cell
state" (page 45). The -i option implements this restriction.
- -2 .. -9
- Scaling: height and with of one cell.
- -a
- Random update of automata, instead of synchronous. Each line
represents one update per automaton on average.
- -d
- Print the transition table on stdout.
- -f
- Fill cells greater than one pixel to touch neighboring units.
- -h value
- The height of the image in lines. Applicable on Unix only, or in
combination with the -x option.
- -n value
- Number of lines to process before displaying the first line.
Applicable in combination with -x option only. Useful for
creating multiple images of different time intervals.
- -p value
- Number of pages. (Not applicable with -x option.) Using a
value of 0 results in ongoing processing, or until the last two lines of
the image are identical.
- -q
- Quiet.
- -r
- Places image in the root window (Unix only). The -h
option has no effect.
- -s value
- Random number seed. The program uses an internal random number
generator. Starting the program with identical random number seed and
other equal parameters results in identical CA's, regardless of the hardware
platform used. When no seed is given, the program selects one using the
current time. This value is displayed, so it can be used to rerun the
simulation, using different values for other parameters, such as lambda.
- -t value
- Number of seconds to pause between pages. Use this if you have a
fast computer.
- -w value
- Combined with the -x option: the width of the image.
- X11 using its own window: width of that window.
- X11 root window: the width of one vertical strip. These strips are
repeated to fill the root window.
- MS-DOS: no effect.
- -x
- Save image in X PixMap format (XPM).
Here's a set of interesting demos. Running one
of the lines as a command results in a complex CA. If you have a fast
computer you should add the option -t1 to the commands.