1
00:00:11,091 --> 00:00:14,798
In, in this one-dimensional Turing machine
2
00:00:14,798 --> 00:00:17,675
each row is another time step,
3
00:00:17,675 --> 00:00:20,060
and so the space-time diagram
4
00:00:20,060 --> 00:00:21,541
is two-dimensional.
5
00:00:21,541 --> 00:00:23,107
We have one space dimension
6
00:00:23,107 --> 00:00:24,373
and one time dimension.
7
00:00:24,373 --> 00:00:27,257
So, what about another question
8
00:00:27,257 --> 00:00:28,940
in two dimensions,
9
00:00:28,940 --> 00:00:30,741
which is analagous
10
00:00:30,741 --> 00:00:34,706
to our NP-Complete question
11
00:00:34,706 --> 00:00:35,923
that we had of whether
12
00:00:35,923 --> 00:00:38,373
tiles of a certain shape
13
00:00:38,373 --> 00:00:39,923
can be placed
14
00:00:39,923 --> 00:00:42,273
to fill in with no gaps or overlaps
15
00:00:42,273 --> 00:00:45,352
a certain target overall shape.
16
00:00:45,352 --> 00:00:47,083
But let's ask an infinite version
17
00:00:47,083 --> 00:00:48,678
of this question.
18
00:00:48,678 --> 00:00:50,455
So, Wang tiles
19
00:00:50,455 --> 00:00:51,821
are little squares
20
00:00:51,821 --> 00:00:53,387
where on each of their edges
21
00:00:53,387 --> 00:00:54,921
there is a color,
22
00:00:54,921 --> 00:00:57,055
and, when we stick them together,
23
00:00:57,055 --> 00:00:58,654
these colors have to match
24
00:00:58,654 --> 00:01:01,235
along their shared edge.
25
00:01:01,235 --> 00:01:03,470
So, there's a nice question here,
26
00:01:03,470 --> 00:01:04,418
if I give you
27
00:01:04,418 --> 00:01:06,286
a finite set of these Wang tiles,
28
00:01:06,286 --> 00:01:07,653
I can ask you,
29
00:01:07,653 --> 00:01:09,139
can you cover the entire
30
00:01:09,139 --> 00:01:11,218
two-dimensional plane with them--
31
00:01:11,218 --> 00:01:13,336
an infinite configuration
32
00:01:13,336 --> 00:01:16,352
where every place where two tiles meet,
33
00:01:16,352 --> 00:01:17,951
their colors match.
34
00:01:17,951 --> 00:01:20,069
In this particular example,
35
00:01:20,069 --> 00:01:23,568
we can cover this 3x3 square
36
00:01:23,568 --> 00:01:25,351
and then we notice something nice:
37
00:01:25,351 --> 00:01:27,701
the colors along the top row
38
00:01:27,701 --> 00:01:29,467
match those along the bottom row,
39
00:01:29,467 --> 00:01:31,269
and the colors along the left edge
40
00:01:31,269 --> 00:01:33,284
match those along the right edge,
41
00:01:33,284 --> 00:01:35,099
which means that we can repeat
42
00:01:35,099 --> 00:01:37,601
this configuration infinitely
43
00:01:37,601 --> 00:01:39,699
and cover the entire plane
44
00:01:39,699 --> 00:01:42,798
with this periodic configuration.
45
00:01:42,798 --> 00:01:43,681
All right.
46
00:01:43,681 --> 00:01:45,548
But, when can you do this
47
00:01:45,548 --> 00:01:47,081
and when can't you?
48
00:01:47,081 --> 00:01:48,182
Well, guess what?
49
00:01:48,182 --> 00:01:50,848
Wang tiles can simulate a Turing machine.
50
00:01:50,848 --> 00:01:52,931
Here's a little sketch of how to do this.
51
00:01:52,931 --> 00:01:55,281
Some of our tiles represent
52
00:01:55,281 --> 00:01:56,898
tape symbols,
53
00:01:56,898 --> 00:01:59,180
and they're colored in such a ways
54
00:01:59,180 --> 00:02:01,120
that we go from one row to the next,
55
00:02:01,120 --> 00:02:03,313
they simply repeat that tape symbol,
56
00:02:03,313 --> 00:02:05,419
carrying it across to the next step
57
00:02:05,419 --> 00:02:06,889
of the computation.
58
00:02:06,889 --> 00:02:08,329
Some other tiles
59
00:02:08,329 --> 00:02:09,696
represent a combination
60
00:02:09,696 --> 00:02:12,466
of a tape symbol and a head,
61
00:02:12,466 --> 00:02:14,228
the head of the Turing machine,
62
00:02:14,228 --> 00:02:16,546
which is in a particular state.
63
00:02:16,546 --> 00:02:18,494
And, we again arrange the colors
64
00:02:18,494 --> 00:02:20,843
so that the only way to continue
65
00:02:20,843 --> 00:02:22,510
the tiling from one row to the next
66
00:02:22,510 --> 00:02:24,394
is to carry out one step
67
00:02:24,394 --> 00:02:25,759
of the Turing machine,
68
00:02:25,759 --> 00:02:27,310
both updating the tape symbol
69
00:02:27,310 --> 00:02:29,275
and updating the state.
70
00:02:29,275 --> 00:02:31,808
So, this means
71
00:02:31,808 --> 00:02:35,159
that asking whether I can tile
72
00:02:35,159 --> 00:02:36,475
the entire plane,
73
00:02:36,475 --> 00:02:38,581
corresponds to the halting problem
74
00:02:38,581 --> 00:02:40,874
because if each row is a new step
75
00:02:40,874 --> 00:02:42,256
of the Turing machine,
76
00:02:42,256 --> 00:02:43,907
suppose I arrange things so that
77
00:02:43,907 --> 00:02:45,915
the halting state
78
00:02:45,915 --> 00:02:47,524
is some kind of gap
79
00:02:47,524 --> 00:02:49,724
with no allowed tile
80
00:02:49,724 --> 00:02:50,874
that I can fit in there.
81
00:02:50,874 --> 00:02:52,547
Well, then, the question of whether
82
00:02:52,547 --> 00:02:54,973
I can continue the tiling forever
83
00:02:54,973 --> 00:02:56,410
and cover the entire plane
84
00:02:56,410 --> 00:02:58,040
is exactly the question of whether
85
00:02:58,040 --> 00:03:00,123
the Turing machine will run forever
86
00:03:00,123 --> 00:03:01,989
and never halt.
87
00:03:01,989 --> 00:03:03,857
Now, there is a catch,
88
00:03:03,857 --> 00:03:05,872
which you may have already noticed.
89
00:03:05,872 --> 00:03:09,038
If you hand me this bunch of tiles,
90
00:03:09,038 --> 00:03:11,738
and ask me whether I can tile the plane,
91
00:03:11,738 --> 00:03:13,389
why can't I cheat,
92
00:03:13,389 --> 00:03:14,894
and just avoid the head of the
93
00:03:14,894 --> 00:03:16,771
Turing machine completely,
94
00:03:16,771 --> 00:03:18,071
and cover the entire plane
95
00:03:18,071 --> 00:03:19,754
with just an empty tape,
96
00:03:19,754 --> 00:03:21,888
which is repeating the same symbol
97
00:03:21,888 --> 00:03:22,988
over and over,
98
00:03:22,988 --> 00:03:24,587
with no Turing machine in sight
99
00:03:24,587 --> 00:03:26,220
reading or writing anything
100
00:03:26,220 --> 00:03:28,901
or with any danger of halting.
101
00:03:28,901 --> 00:03:30,903
Well, this is a good point,
102
00:03:30,903 --> 00:03:33,669
and, in fact, when the Wang tiles
103
00:03:33,669 --> 00:03:36,075
were first invented, it was conjectured
104
00:03:36,075 --> 00:03:37,985
that any set of tiles
105
00:03:37,985 --> 00:03:39,802
that could tile the plane at all,
106
00:03:39,802 --> 00:03:42,052
could do so periodically.
107
00:03:42,052 --> 00:03:44,497
And if you think about it,
108
00:03:44,497 --> 00:03:46,702
if that were so,
109
00:03:46,702 --> 00:03:48,284
then the tiling problem would be
110
00:03:48,284 --> 00:03:50,250
decidable.
111
00:03:50,250 --> 00:03:51,817
Because we would just look at
112
00:03:51,817 --> 00:03:53,448
larger and larger areas,
113
00:03:53,448 --> 00:03:54,750
and we would eventually
114
00:03:54,750 --> 00:03:56,749
either find an area which we could tile
115
00:03:56,749 --> 00:03:58,783
in a way that we can repeat everywhere,
116
00:03:58,783 --> 00:04:00,366
because the colors match along,
117
00:04:00,366 --> 00:04:01,549
just as before,
118
00:04:01,549 --> 00:04:03,269
match along the top and bottom edges
119
00:04:03,269 --> 00:04:04,732
and the left and right edges,
120
00:04:04,732 --> 00:04:05,466
or,
121
00:04:05,466 --> 00:04:07,015
we would reach a finite area
122
00:04:07,015 --> 00:04:08,435
which can't be tiled at all,
123
00:04:08,435 --> 00:04:09,582
and one way or the other
124
00:04:09,582 --> 00:04:10,898
we would know.
125
00:04:10,898 --> 00:04:12,697
But that conjecture was wrong.
126
00:04:12,697 --> 00:04:16,014
There are aperiodic tilings.
127
00:04:16,014 --> 00:04:17,980
There are sets of tiles that can cover
128
00:04:17,980 --> 00:04:19,180
the entire plane,
129
00:04:19,180 --> 00:04:20,430
but only do so
130
00:04:20,430 --> 00:04:22,167
in a funky way
131
00:04:22,167 --> 00:04:24,713
which never quite repeats.
132
00:04:24,713 --> 00:04:26,461
So here is a picture
133
00:04:26,461 --> 00:04:28,746
of the classic Penrose tiles,
134
00:04:28,746 --> 00:04:31,187
with these kites and darts
135
00:04:31,187 --> 00:04:32,646
which, because of their local
136
00:04:32,646 --> 00:04:34,078
5-way symmetry
137
00:04:34,078 --> 00:04:37,828
have to tile the plane aperiodically,
138
00:04:37,828 --> 00:04:39,828
because there's no periodic tiling
139
00:04:39,828 --> 00:04:41,740
with perfect 5-way symmetry.
140
00:04:41,740 --> 00:04:43,223
Now, I wanted to show you these
141
00:04:43,223 --> 00:04:44,507
because they're beautiful,
142
00:04:44,507 --> 00:04:45,292
but,
143
00:04:45,292 --> 00:04:47,444
the Wang tiles is really more of
144
00:04:47,444 --> 00:04:49,143
a question about square grid,
145
00:04:49,143 --> 00:04:50,727
so, can we do something similar,
146
00:04:50,727 --> 00:04:54,644
with tiles that line up with each other
147
00:04:54,644 --> 00:04:55,974
on a square grid,
148
00:04:55,974 --> 00:04:58,277
but somehow because of their colors,
149
00:04:58,277 --> 00:04:59,092
or their shapes,
150
00:04:59,092 --> 00:05:01,292
or maybe little doodads we add to them,
151
00:05:01,292 --> 00:05:03,075
they only tile the grid
152
00:05:03,075 --> 00:05:05,490
in an aperiodic way.
153
00:05:05,490 --> 00:05:07,092
Well indeed this is possible,
154
00:05:07,092 --> 00:05:09,108
and this is a particular setup
155
00:05:09,108 --> 00:05:11,406
discovered by the logician
156
00:05:11,406 --> 00:05:13,778
Raphael Robinson.
157
00:05:13,778 --> 00:05:16,607
These tiles can only cover the grid
158
00:05:16,607 --> 00:05:19,472
in a particular fractal pattern,
159
00:05:19,472 --> 00:05:21,890
and so with this fractal pattern
160
00:05:21,890 --> 00:05:23,273
we can with a little work
161
00:05:23,273 --> 00:05:24,273
force
162
00:05:24,273 --> 00:05:26,390
the Turing machine we're simulating
163
00:05:26,390 --> 00:05:28,907
to first of all, exist
164
00:05:28,907 --> 00:05:31,089
by demanding that there is a head
165
00:05:31,089 --> 00:05:33,572
there at the upper left-hand corner,
166
00:05:33,572 --> 00:05:36,355
and we can force it to attempt
167
00:05:36,355 --> 00:05:38,905
longer and longer computations
168
00:05:38,905 --> 00:05:40,620
until if at some point it halts,
169
00:05:40,620 --> 00:05:42,311
there will be a place in the tiling
170
00:05:42,311 --> 00:05:43,970
that we cannot fill in.