using cellular automata
A little history
In the 1940’s, at what is now the Los Alamos National Laboratory (LANL), the mathematician
John von Neumann
working on the problem of self-replicating systems
, such as those found in biology
or cybernetics. At the same time his friend and colleague at LANL, Stanislaw Ulam
, was studying a related problem of crystal
growth. Ulam was using what today would be called a computer simulation technique.
He represented the crystal surfaces as nodes in a lattice network
and using one of the early computers built
for the Manhattan Project, probably the ENIAC, he observed the changes to the surfaces
as the nodes obeyed rules that he imposed on them. (This is supposition on my part:
I have not actually seen any of Ulam’s publications related to this work.) Ulam
suggested to von Neumann that he try a similar computational approach to the study
of self-replicating systems. Von Neumann adopted this approach and gave the concept
the name Cellular
(CA). He did considerable work with CA and in 1966 published a
book entitled The Theory of Self-Reproducing Automata.
[A.W. Burks (ed),
Univ. of Illinois Press]. In the 1970’s CA surfaced in the popular culture in the
form of the mathematician John Conway’s Game of Life
largely as a result of Marvin Gardner's article
in Scientific American: The Fantastic Combinations of John Conway’s New Solitaire
[Sci. Am., 223:120-123,1970]. In the 1980’s considerable work
was done on CA by
. The concepts of CA are a central theme of his book A New Kind of Science
[Wolfram Media, Inc.,
2002]. This book contains a complete history of CA as well as a full exposition
of the science and mathematics associated with CA. The rules used to identify CA
that are defined in Wolfram’s book are the rules I have used in my program CA Pattern
. In fact, Wolfram’s book was in large part the inspiration for the
development of this program.
What are Cellular Automata?
The analytical (pencil and paper) way to solve for the state of physical systems
undergoing change is to solve differential equations that assume space and time
are continuous quantities. Computer simulations of these systems, on the other hand,
divide space and time into discrete elements. The elements of space are called “cells”
and the elements of time are called “steps”. CA are arrays of cells whose state
at a particular time step depends automatically and only on its own state and the
state of its neighbor cells at the previous step. If the CA array is confined to
a line where the neighbors are just the ones to the Left and Right, the CA is said
to be one dimensional. Two dimensional CA arrays can involve just 4 neighbors (North,West,South
and East) or all 8 neighbors including the diagonals (N,NW,W,SW,S,SE,E,NE). In principle
the cells within the CA can have any number of states. Von Neumann’s self-reproducing
robots, for example, had 29 states. But the CA cells we are considering here have
only 2 states: dead or alive, empty or filled, white or colored, or, in the usual
computer parlance, 0 or 1. The rules that the CA obey as they evolve are coded as
a set of integer numbers according to the schemes defined in Wolfram's book. I have
included a detailed explanation of how the integer codes relate to the rules imposed
on 1D and 2D CA on a separate page.
You can view a collection of CA patterns here
. The captions
for 1D CA patterns give the rule number; e.g., CA161. For 2D patterns, the caption
gives the rule number and number of steps; e.g., CA491_66 which means 4 neighbor
rule 491 run for 66 steps. Patterns using 8 neighbor rules have captions like CA8_174826_200,
meaning 8 neighbor rule 174286 run for 200 steps. Captions where the steps are given
like 46x6 means the pattern was run for 46 steps 6 times in a row (very different
from 276 steps all at once.)
A cross-platform (browser based) version of CA Pattern Maker
has been developed
work on modern smartphones.
Operating the Program
You can adjust the settings for the three stages of pattern setup:
You can create your own palette of colors and/or change the background color of
the pattern using a color-picker;
You can define how the colors in the palette are sequenced through the time steps
required to generate the pattern: randomly, uniformly with a specified number of
steps per color, using the Fibonacci sequence where the steps per color progress
through a specified portion of the Fibonacci sequence, or custom, where you choose
the number of steps for each color in the palette.
You can choose to generate 1D or 2D patterns or to play Conway's Game of Life.
You can specify the size of the cells (in pixels) and the rule
(code) for the 1D and 2D CA.
The size of the 2D patterns is fixed by adjusting the number of steps and.or the cell size.
3)Initial cell positioning:
For the 1D and 2D CA you can choose to have the starting cell positioned at the
center, you can manually position any number of starting cells, or, in 1D, you can
randomly position the initial cells.
For the Game of Life you can select among a set of established starting patterns
or create your own custom pattern.
For additional information see Notes and suggestions.