we've seen that Babbage and Lovelace's mechanical
devices could compute
that cellular automata can compute
that even Wang tiles that are trying to
fit together and cover the plane
can compute
what about dynamical systems?
here is a diagram of a chaotic
dynamical system called the "Baker's map"
What it does, is it takes points that lie
in the unit's square, so X and Y both range
from 0 to 1
It stretches, the square
then cuts off the top half
and puts it down here
on the right
so it stretches, cut, puts it down on the right
stretches, cuts, puts it down on the right
each time you run it
so as a result
the X coordinate, in every step is getting squeezed,
the Y coordinate in every step is getting stretched
but if it's bigger than '1'
it gets cut off and put back down
so we can write this down mathematically
by saying that in each step
Y becomes 2Y mod 1
where...by mod 1 I mean
if it's bigger than integer 1
subtract 1 so that you again get a real number
between 0 and 1
X goes from X to X over 2 (X/2)
if you're in the bottom half of the square
cause then you just get smooshed over here
and it goes over to x over 2 (x/2) plus a half (1/2)
because, if you're in the top half
of the square
because then you get stretched
over here, and then put down there on the right side
so...
why is this an interesting dynamical system?
well, for one thing, it's chaotic
if you have two initial conditions
which are quite close to each other
then unless their Y coordinates are exactly the same
each time we stretch in the Y direction
the difference along the Y axis
will get twice as big, twice as big, twice as big,
until eventually
one is in the top half, and one is in the bottom half
and after that their in essentially
unrelated places
so these small differences
in initial conditions
will get exponentially amplified
over time
which is one definition of chaos
in dynamical systems
now...
let's do something kind of cute
to the binary digit sequences
of the X and Y axis
the X and Y coordinates
so I'm going to
take that decimal point, or binary point
and write the X coordinate
over here
the half's digit, the quarter's digit, the X's digit
and so on
so I'm gonna take that real number
and write it to the right of the decimal point
as I normally would
but in base 2 instead of base 10
I'm gonna take the Y coordinate and do the same thing
backwards
so it constitutes, the left side of my sequence
in fact I claim this is a particularly simple example
of a Turing machine
so one of the things we're doing
to X,
is dividing it by 2,
so if you have a number
written out in binary
and you divide it by 2
it's going to shift all those bits down
away from the decimal point
leaving space up here
at the half's digits
but what do we put there?
well... we add a half to X putting a 1 here
if Y was bigger than a half
but Y being bigger than a half
well, that is if the half's digit of Y is 1
so this entire operation
consists of
shifting over
the decimal point
taking the half's digit of Y
and moving it into the half's digit of X
so this is a particularly simple Turing machine
where the decimal point is the current location of the head
and all it does
is move left
transferring bits from the Y coordinate
over to the X coordinate
it doesn't read or write them, or modify them in any way
now, let's simulate a Turing machine which does
read and write
which has a couple of internal states
and which actually does something to these bits
well as you can imagine, we're going to get
a more complicated version
of this dynamical system
like this one
so here at the top we have this rectangle
it's divided into a bunch of squares and rectangles
which represent combinations
of the tape symbols
which are bits
and the internal state of the Turing machine
if we move left then these squares and rectangles get stretched
this way
and squashed that way
if we move to the right
then they get stretched this way and squashed that way
and then to read and write
and to change the internal state
we're going to displace some of these rectangles
from one place to another
so...
if you follow this map
if you continue
iterating
every time you have a point in that top rectangle
you follow the map and figure out where it should go
then you do it again, and
again, and again,
you're literally carrying out
steps of a Turing machine computation
and in particular
a small universal Turin machine
so,
And by the way this kind of thing was in my PhD thesis
I guess I'm ringing my own bell here, but...
the point is
that this dynamical system
which is not that much more complicated than
the class Baker's map
is doing universal computation
as a result
All of it's long term behavior is
undecidable
so even if I describe this map to
with perfect accuracy telling you exactly
where all these rectangles lie
and where they endup
and I give you an initial point
X, Y
somewhere in this rectangle
it is undecidable
uncomputabl, to tell whether, as we iterate the map
it will ever fall into a particular region
because that region
could correspond to the halt state
it is undecidable to tell whether that point is periodic
whether it will ever return to where it began
it's undecidable to tell whether it lies on a chaotic
tragectory
if indeed it is one of those points
where a small predation
to that initial condition
will cause a big and exponentially growing
difference down the road
since all of these questions correspond to the
halting problem
they're all undecidable
and I wanna point out
this is worse than the type of unpredictability
we usually have in chaotic dynamical systems
usually what we say
you know, butterfly flapping its wings
causing a hurricane six months late, etc, etc,...
usually what we say is that chaotic dynamical systems
are hard to predict because we don't know things exactly
and even a small error
in the initial condition
will get exponentially amplified over time
until we really have no idea
where in the system
state space it is
this is different
these undecidability holds, even if the initial condition
is rational with the finite number of binary digits
even if we know it exactly and can write it down
with no error what so ever
so
this is a very strong type of unpredictability
that comes from undecidability
I want to end this unit by just pointing out
there's a lot of naturally occuring
dynamical systems
which seem difficult to classify computationally
here is another chaotic map
in 2 dimensions called
the standard map
you can see it is all kind of complicated structure
all sorts of basins and periodic orbits
where it can get stuck for long periods of time
slowly escape from them
and end up somewhere totally different
it seems hard to predict
it is hard for me to imagine
an algorithm
which can look forward in time
much faster than we could by literally
simulating it in step by step
I highly doubt that there's any shortcut
to predicting the eventual fate of an initial point as we apply this map over and over again
on the other hand
I don't see how to build a computer
out of it either
it seems too messy
it doesn't have these clean boundaries
like the ones we designed into that map
I showed you before
with those rectangles and squares
corresponding precisely
to some combination of a tape symbol
and a Turing machine state
and a transition
which corresponds precisely
to writing some new symbol
and updating the state
so it's possible
that the long term behavior of
naturally occurring systems like this
is undecidable, but not universal
there maybe no algorithm
to predict what will eventually happen
at the same time
it may not be the case that we can
translate
the halting problem
into a problem of..
into a question about this chaotic dynamical system
there maybe no way to reduce halting to that
long term question
so many, dynamical systems occurring in the real world might be in this messy middle ground
where they're too complicated to predict
we just have to simulate them and see what happens
but
they're not controlled enough to actually
use to build a computer out of
and thus prove that their long term behavior is uncomputable
that would be a funny situation to be in
because there would be no algorithm to predict them
but we would have no way to prove
that there's no algorithm to predict them
because it wouldn't correspond to the halting problem