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