Let's look more closely at the idea that
Cellular Automata are dynamical systems
analogous to the logistic map.
Well here is a point by point comparison .
In the logistic map we have this equation where
the value of x at t+1 is some function
of the value of x at time t.
And here is our familiar equation.
Well similarly, elementary CA's
and other kinds of Cellular Automata
we have our state of the world
which is our lattice configuration
of black and white cells,
and the lattice configuration at time t+1
is a function of the lattice configuration
at the previous time step.
Here the function is represented by the rule
that's taking neighborhoods
and updating the center cell.
Both logistic map and elementary CAs are
completely deterministic,
there is no randomness involved.
They both iterate in discrete time steps
In the logistic map we have
a continuous state.
That is the value of x is a real number,
whereas the Cellular Automata
the lattice configuration is a discrete state,
it's a sequence of black and white cells
The dynamics of the logistic map we saw
went from fixed point, to periodic, to chaos.
We saw all those kinds of dynamics,
and similarly in Cellular Automata,
especially here the elementary automata
we saw those same kind of dynamics,
fixed point, periodic and chaos.
In the logistic map we had what's called
the control parameter, r,
that is as we moved r from 0 to 4
we saw that the dynamics
of the system started out a fixed point,
and moved through periodic attractors
through a period doubling path
all the way to chaos.
Well, what's the control parameter for
elementary or other cellular automata.
It is clearly not the Wolfram number.
The Wolfram number doesn't order
the cellular automata in any order which
corresponds to their behavior, it's arbitrary.
So people started thinking about what
would be a control parameter that
would play the same role as r.
Where as you increased the value
of the parameter you go through
these different kinds of dynamic behaviors.
Chris Langton is a complex system scientist
who worked on cellular automata extensively,
and came up with this idea called
the lambda parameter
as a proposed control parameter
for celllular automata.
For two state cellular automata,
the kind we have been looking at,
that is each cell is either black or white,
lambda is very simply defined
as the fraction of the black output states
in a rule table.
So, for example, given this rule table
we would count up in this column
of output states, we have one, two, three,
four, five, over eight total.
So that lambda here is five eighths.
So that is a really simple definition,
but Langton was able to show
that in some cases the lambda value of
the cellular automaton was
a fairly good predictor of its behavior.
Langton's hypothesis was that
the typical behavior of cellular automata
with a given lambda value
would go along with this scale.
From fixed point behavior at lower levels
of lambda, and as lambda is increased .
we would see periodic
and then chaotic behavior
Of course, because cellular automata
have two states white and black
they're symmetric in that,
for example, a lambda of 0,
which would mean all white fixed points,
is basically equivalent behavior to a
lambda of one which is all black
fixed points.
So if you reversed the white and black
colors in the update states you get
the same or equivalent behavior
just with the colors reversed.
This is a little different than r
in that we have this symmetry.
Langton did extensive simulations to test
his hypothesis and found that lambda
tends to be a better predictor of behavior
for cellular automata that are not elementary,
that those with neighborhood size
greater than three cells.
We are going to look at the relationship
between lambda and cellular automaton
behavior using an applet that was developed
at the math departments of
Hobert and William Smith colleges
This link is also on the
course materials page.
On this page you can watch
the Edge of Chaos simulation
it's a JAVA applet
and It has some complicated options
that you can use.
To make it simple I'm going
to get a new world.
I'm going to have the number of states
be two, that is black and white,
and we'll have the neighborhood size be 5.
So each cell communicates
with two cells on either side of it.
So these are still one dimensional
cellular automata.
We are going to say no rules are
not isotropic.
yYou can read about that in the website,
that just means that we are going
to use the most general rules,
the world is circular, and so on.
OK, so we are going to create a world,
and now what we can do is slide
lambda using this slider.
So when lambda is zero
this random initial configuration
which you can barely see here
always updates to what?
Well, we can do the same thing by having a new random world .
that just creates a new random initial configuration,
and so on. So we can slide lambda up
and see these sort of how it changes.
So here we have a fixed point of all white
and we keep moving it slowly,
each time I do this what
the simulation does is picks a
new cellular automaton that has
this lambda value.
Of course, there is more than one cellular
automaton that has this lambda value,
but its picking one at random
Right now I'm starting to get
periodic behavior, and still periodic,
it may be a little more complicated,
so I'm sliding this up, sliding ... sliding OK.
Well, one interesting perhaps more
interesting, and good comparative thing
Is to have, let's see ... start with one dot.
That's just starting with one cell, black.
All right, so I keep going here, still periodic.
Now I'm getting something a little
more complicated.
Alright split that, well this is starting to look a
little more like a random or chaotic pattern.
I move it a little bit
further up, and so on, until I moved it
way to the middle, and now things
are just looking really, really random
So you can play with this,
and what Langton did was
he implemented his own version of this
and did extrensive experiments by
looking at random choices of cellular
automata, for various lambda values,
and found that lambda was a fair predictor
of the types of dynamics that you
are likely to see.
Now there might be certain initial
configurations that give different behavior
than other initial configurations
with the same cellular automaton,
but his concern was on average the behavior
Well, I've been using the word chaos a
little loosely here.
To what extent is the random looking
behavior we see is actually chaotic.
Namely, does it have sensitive dependence
on initial conditions.
Well, Norman Packard investigated that,
and what he did was he looked at different
cellular automata, here with
seven-cell neighborhoods, That is each
cell looks at three neighbors on either side.
For each lambda value, he tested a number
of randomly selected cellular automata
with that lambda value with a number of
random initial conditions, and he computed
the average difference, spreading rate
which is a measure of sensitivity
to initial conditions.
Basically you take the same cellular
automaton and start it with very close
initial conditions, maybe one bit away from
each other, one black cell turned
to a white cell, and see how fast
the two spread apart in behavior.
There is a measure for that.
He plotted this as a function of lambda
and you find here you have very
ordered behavior, and here you have kind
of a transition to more chaotic behavior,
and here you really have chaos, with
sensitive dependence on initial configurations.
Indeed, you do get this kind of behavior
that Langton hypothesized
and Packard showed in his experiments.
Packard called these regions
the Edge of Chaos that is, the place where
things are not completely ordered,
and yet they are not completely random,
and this corresponds roughly to
Wolfram's class 4.
That is, those interesting cellular automata
with long lived, localized structures,
such as in rule 110.
So in summary, cellular automata
can be viewed as dynamical systems
with different kinds of attractors
such as fixed point, periodic, chaotic,
and what we might call the edge of chaos.
And these correspond to
Wolfram's four classes.
Langton's lambda parameter is one
proposed control parameter that roughly
indicates what type of attractor to expect.
Other people have proposed other
control parameters related to lambda that
do sometimes a better job at predicting.
The Game of Life is a class 4 cellular automaton.
It has all the properties that
Wolfram listed for Class 4 cellular automaton.
Now Wolfram hypothesized that
Class 4 cellular automata are
capable of universal computations
which is something I will talk about
in the next subunit.