In, in this one-dimensional Turing machine
each row is another time step,
and so the space-time diagram
is two-dimensional.
We have one space dimension
and one time dimension.
So, what about another question
in two dimensions,
which is analagous
to our NP-Complete question
that we had of whether
tiles of a certain shape
can be placed
to fill in with no gaps or overlaps
a certain target overall shape.
But let's ask an infinite version
of this question.
So, Wang tiles
are little squares
where on each of their edges
there is a color,
and, when we stick them together,
these colors have to match
along their shared edge.
So, there's a nice question here,
if I give you
a finite set of these Wang tiles,
I can ask you,
can you cover the entire
two-dimensional plane with them--
an infinite configuration
where every place where two tiles meet,
their colors match.
In this particular example,
we can cover this 3x3 square
and then we notice something nice:
the colors along the top row
match those along the bottom row,
and the colors along the left edge
match those along the right edge,
which means that we can repeat
this configuration infinitely
and cover the entire plane
with this periodic configuration.
All right.
But, when can you do this
and when can't you?
Well, guess what?
Wang tiles can simulate a Turing machine.
Here's a little sketch of how to do this.
Some of our tiles represent
tape symbols,
and they're colored in such a ways
that we go from one row to the next,
they simply repeat that tape symbol,
carrying it across to the next step
of the computation.
Some other tiles
represent a combination
of a tape symbol and a head,
the head of the Turing machine,
which is in a particular state.
And, we again arrange the colors
so that the only way to continue
the tiling from one row to the next
is to carry out one step
of the Turing machine,
both updating the tape symbol
and updating the state.
So, this means
that asking whether I can tile
the entire plane,
corresponds to the halting problem
because if each row is a new step
of the Turing machine,
suppose I arrange things so that
the halting state
is some kind of gap
with no allowed tile
that I can fit in there.
Well, then, the question of whether
I can continue the tiling forever
and cover the entire plane
is exactly the question of whether
the Turing machine will run forever
and never halt.
Now, there is a catch,
which you may have already noticed.
If you hand me this bunch of tiles,
and ask me whether I can tile the plane,
why can't I cheat,
and just avoid the head of the
Turing machine completely,
and cover the entire plane
with just an empty tape,
which is repeating the same symbol
over and over,
with no Turing machine in sight
reading or writing anything
or with any danger of halting.
Well, this is a good point,
and, in fact, when the Wang tiles
were first invented, it was conjectured
that any set of tiles
that could tile the plane at all,
could do so periodically.
And if you think about it,
if that were so,
then the tiling problem would be
decidable.
Because we would just look at
larger and larger areas,
and we would eventually
either find an area which we could tile
in a way that we can repeat everywhere,
because the colors match along,
just as before,
match along the top and bottom edges
and the left and right edges,
or,
we would reach a finite area
which can't be tiled at all,
and one way or the other
we would know.
But that conjecture was wrong.
There are *aperiodic* tilings.
There are sets of tiles that can cover
the entire plane,
but only do so
in a funky way
which never quite repeats.
So here is a picture
of the classic Penrose tiles,
with these kites and darts
which, because of their local
5-way symmetry
have to tile the plane aperiodically,
because there's no periodic tiling
with perfect 5-way symmetry.
Now, I wanted to show you these
because they're beautiful,
but,
the Wang tiles is really more of
a question about square grid,
so, can we do something similar,
with tiles that line up with each other
on a square grid,
but somehow because of their colors,
or their shapes,
or maybe little doodads we add to them,
they *only* tile the grid
in an aperiodic way.
Well indeed this is possible,
and this is a particular setup
discovered by the logician
Raphael Robinson.
These tiles can only cover the grid
in a particular fractal pattern,
and so with this fractal pattern
we can with a little work
force
the Turing machine we're simulating
to first of all, exist
by demanding that there is a head
there at the upper left-hand corner,
and we can force it to attempt
longer and longer computations
until if at some point it halts,
there will be a place in the tiling
that we cannot fill in.