Cellular Automata

[example] Contents:

Literature

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

What are cellular automata?

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.

Software

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).

Demos

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.