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.