# Wolfram's Cellular Automata

## Cellular Automata

Let us consider one-dimensional cellular automata for
simplicity. Cells are connected as a chain. Each cell is
numbered from 0 (left) to N-1 (right). Each cell is given a
integer value from 0 to k-1. The state of cell i at time t is
denoted s[i](t).

The value of a cell i is updated by the following rule:

s[i](t+1)=F(s[i-r](t),s[i-r+1](t),...s[i](t),..,s[i+r](t))

The state of a cell i is updated depending on 2*r+1 neighboring
sites. The function F should be common for all cells. The
function F is called the update rule.

The system is discrete both in time and space. The state of
a cell is finite. States of all cells are updated parallelly.

## Wolfram's Cellular Automata

Let us consider a simpler case. The number of state is k=2.
Namely the state takes only two values, 0 and 1. And a cell
interacts only with its nearest neighbors (r=1).

Because each cell interacts only with its nearest neighbors, the
number of variables in the function F is three. Each variable
takes two values, 0 and 1. So the number of patterns in variables
is eight. Specifying 0 or 1 for each of 8 input patterns
determines the update rule F. Therefore the number of update
rules is 2**8=256.

Symmetric rules in those 256 rules are called Wolfram's
elementary CA (cellular automata). Some of those simple rules can
generate very complex behavior.

Shin-ichi TADAKI
Last modified: Fri Jan 9 10:22:25 JST 2004