Looking at Cellular Automata as computers
is a huge subject, worthy of a course
in and of itself
Here I will give a cursory overview
but I put some readings on
the optional reading section
of the course web page for you
to look at on this topic
Let's first talk about what
we mean by computation.
Computation is the processing of information
In a computation
information is input to the system,
it's stored in memory in some way,
it's transferred from
one part of memory to another,
and it's combined with other information
and this could also be called processed.
Finally, the processed information
is output for the user
or the whole system to use in some way
So a little sketch, we have input,
and then a program which performs
the computation, and then output
Sometimes, for example,
in a dynamical system
the output would go back
and become the input.
There is a notion that's very important
in the field of computer science
and in the field of complex systems
which is the notion of the universal computation.
Basically universal computation
is the phenomenon of
a computer being able to be programmed.
That is a universal computer
is a computer that can run any program.
So it's like the computer on your desk
if it only had an infinite amount of memory
Then it could run any possible program
and compute any possible function
that was computable.
So the idea here is that instead of just input
we have an input and a program
This goes into a universal computer
and the result is an output
You can think of this as the computer
on your desk were you can input your data
there is a program that's been input
either by you or by somebody else
that's in the memory of your computer.
Your computer acts as a universal computer
and runs that program on that input,
and then it creates the output.
One of the triumphs
of the field of computer science
was the discovery that
only a small set of logical operations
is needed to support universal computations.
By support universal computation
I mean to be able to build
a programmable computer
What this means is that if you can implement
a particular set of logical operations,
use them, and combine them in different ways
You'll be able in principal to have
a computer that can run
any program on any input,
that is a universal computer
As I mentioned earlier,
John Von Nuemann was one of the first
scientist to look at cellular automaton
as models of complex systems
and in particular
he was looking at the idea of
self reproduction in machines or automata.
He built a cellular automaton,
a two dimensional one.
Each cell could be in one of 29 states,
and this cellular automaton
could replicate any pattern
that was input to it including itself.
This is a schematic picture
of this kind of self reproduction,
here is a complicated machine.
It has a input space, output space,
and it creates a copy of itself.
or any other pattern that you give it.
but Von Nuemann also made it
into a universal computer.
That is, this can not only self-replicate
it can compute any computable function.
Many people have simplified Von Neumann's
self-reproducing automaton
to have fewer states, but it was
the first creation of a universal computer
inside a cellular automaton
The Game of Life has also been shown
to support universal computation
In 1970 John Conway showed that Life
can implement the simple logic operations
that are needed in principle
for universal computation.
He also sketched how
a universal computer can be constructed.
Then in the 1990s , Paul Rendell
constructed the universal computer
Here is a picture of part of
the universal computer that he constructed
A little hard to see,
but it uses some of those structures
we looked at earlier
Such as gliders, glider guns, and so on
to implement these logical operations
needed for universal computation
I have to say that this is
a fantastically complicated undertaking
to actually implement this kind
of computation in a cellular automaton.
For a long time, Stephen Wolfram suspected
that some elementary cellular automata
could support universal computation
This would be significant
in that elementary cellular automata,
if you recall, are extremely simple
and the question was could
the complex behavior that they created
be complex enough
to implement this most powerful form
of information processing
Well, Wolfram's hypothesis was
that all class 4 cellular automata
can support universal computation.
Remember, class 4 were those
in between periodic and chaotic,
those Edge of Chaos cellular automata.
This hypothesis is hard to evaluate.
Well, one problem is
that there is not really
a formal definition of Class 4
cellular automata.
Also, it turns out to be very hard
to actually prove that some system
is capable of universal computation
However, Wolfram and his colleague,
Matthew Cook, were successful
in proving that Rule 110
can support universal computation
This proof was described in a long chapter
of Wolfram's book, A New Kind of Science
You can actually read this for free online
I put a link at our course materials web page.
It's a rather technical proof but
the general idea is that Rule 110
supports these so called moving particles,
that is these localized structures
that move in space and time,
Remember, time goes down the vertical
space goes along the horizontal
in one dimension,
and so, these moving particles
can integrate information
from different spatial locations
and collide with one another.
So, for example, we see here
this particle colliding with this particle
and creating a new particle
The idea is that information can be stored
in these more regular patterns,
transferred via these particles,
and processed via the particle collisions
In principle, these can support
a universal computation
In practice, however, it's hard
if not impossible to actually program
these cellular automata to do
any useful task
Well, universal computation
in cellular automata is very interesting,
and even surprising given how simple
they are, especially the elementary CAs.
It's not very practical way
to perform computation.
It's too slow to simulate
a universal computer
in a cellular automaton
It's also to hard to program.
So no one really does computations
for any practical purpose
using the universal computational
abilities of cellular automata.
However, CAs have been harnessed
for more practical parallel computations.
For example, in the field of image processing.
I'm not going to talk much about that here,
but in the next subunit
I'm going to talk about
one particular project
in which genetic algortihms
were used to evolve cellular automata
to perform practical computations.
Finally, let me just say a few words on the significance
of cellular automata for complex systems
Well, you've seen that cellular automata
are really idealized complex systems
that can produce very complex behavior
from simple rules
You've seen that natural complex systems
can be modeled using cellular automata
like architectures,
and that cellular automata
give a framework for understanding
how complex dynamics can produce
collective information processing, that is
information processing that emerges
from a collection of simple components
in a life like system.
Where life like, means decentralized,
relatively simple components,
limited communication,
among components, and so on.