So,
Babbage's machine,
if he could have built it,
would have been able
to carry out
any computation that modern computers can
although it would have needed
a lot of space and a lot of steam.
What else is capable
of universal computation?
Well, in complex systems
we kind of enjoy
and love
these little examples,
these toy universes,
cellular automata.
So, a cellular automaton is something
typically a 1- or 2-dimensional grid
and at each grid location
we have a finite set of states,
and one of our favorite examples
also a popular screensaver
is The Game of Life
invented by John Conway.
So in The Game of Life,
each grid square can be alive or dead.
Here the alive things are black
and the dead things are white.
And, as in all cellular automata,
there is a simple, local rule
where each grid point,
at each step, looks at
its own state and those of its neighbors
and then computes its new state
and everything gets updated in parallel.
In this particular rule,
the neighbors are the 8 locations
in the grid that you could move to
with the move of a chess king
and the rule goes like this:
if you are alive,
and 2 or 3 of your 8 neighbors are alive,
you stay alive.
If fewer than 2 are alive,
you die of loneliness.
If 4 or more are alive,
you die of overpopulation,
goes the story.
This isn't really a biological model,
but. Okay, and
if you are dead, your square is empty,
and you have exactly 3 neighbors
that are alive,
then on the next step
you will be alive.
That's the whole rule.
And Conway played with these
numbers, these thresholds, for
being alive or dead until
it did something fun and interesting,
basically.
So one of the things that happens
in The Game of Life is
a little thing we call a "glider."
It's this little wiggly animal
which travels across diagonally,
and it will keep traveling until it
bumps into something.
Then, there's another thing
called a "glider gun,"
which shuffles back and forth,
and produces a stream of gliders.
And moreover it's possible
to carefully design collisons
between the gliders,
to build small objects,
or even to carry out logical operations.
We can use the gliders,
a stream of gliders,
almost like a wire,
to carry a bit of information.
Well, if you combine
all of these elements,
and you're extremely clever
and you have an abundance of free time,
you can build a Turing machine
out of The Game of Life.
So here we have
a very complicated configuration
in which the pixels are
almost too small to see.
I've zoomed in on
one of the glider guns there,
where, across the diagonal here
we have the Turing machine's tape,
and here we have the head
of the Turing machine.
And so The Game of Life
with a large enough initial configuration,
can simulate a Turing machine.
There are some interesting questions
here about is it okay
to start with a configuration
which is infinite, but periodic.
That gives you all the tape
you could ever possibly need,
or, perhaps there's a clever way
to have glider guns build the tape
over time, starting with
an initial configuration which is blank,
outside of a finite area.
But, anyway.
The Game of Life can compute.
It can compute because I just showed you
how to build a computer in it.
Remember a long time ago
when we were talking about
the NP-Completeness of certain problems
like, ah, like the tiling problem,
fitting in puzzle tiles
into a certain shape,
or the Hamiltonian path problem,
and I emphasized
that these problems are hard because
you can build computers out of them.
Well, here we're building
universal computers,
and given enough space and time,
in a cellular automaton,
we can carry out
*any* computation at all,
not just one in say,
polynomial time or exponential time,
the way we were talking about before.
The Game of Life is a 2-dimensional
cellular automaton,
in which it's fairly easy
to set up a tape,
and a head which moves back and forth
on that tape.
So what about 1-dimensional
cellular automata?
Well, here is a particular
1-dimensional cellular automaton.
Again, we just have 2 states,
0 and 1, or black and white,
at each location,
and, again,
we look at our nearest neighbors
as well as our own state,
and this is the update rule
where I'm showing you
what the new state will be
for the 8 possible neighborhoods,
combinations of your own state
and those of your neighbors.
In fact, this is cellular automaton
Rule 110
because, if these black squares are ones
in the rule
and the white squares are zeroes,
then in binary,
this spells out 110.
And Stephen Wolfram invented
that numbering scheme
as a way of exploring
all cellular automaton rules
of a given size.
So, here is a space-time diagram
of a typical run of Rule 110.
At the top we have
the top row is some initial
setting, of all the cells in the grid,
and time goes downward.
And when you look at this,
what immediately jumps out at you
is there are all kinds of gliders.
There are all sorts of different
particles, if you will, analogous to
the glider in The Game of Life,
but with many types,
which, as we move down,
may move left or right
at various velocities,
and you can see that
when they bump into each other,
complicated things happen.
So, it's tempting to think
that we can build a Turing machine
out of this.
This was conjectured by Stephen Wolfram
and then proved by Matthew Cook,
and the two of them published this paper
and showed that indeed, Rule 110
is capable of universal computation
and, therefore,
its long-term behavior,
what will eventually happen
from some initial state,
is undecidable.
And Turlough Neary and Damien Woods
improved their simulation,
and showed that, in fact, it can simulate
Turing machines with only
polynomial overhead; in other words,
it can simulate t steps
of a Turing machine
with an amount of time
which is only polynomial NT.
That means that predicting it,
even for finite time,
requires you to do a fair amount of work,
about as much work as you
would need to run a Turing machine
for that amount of time.