1
00:00:01,200 --> 00:00:07,250
Since the time of the ancient Greeks, the best ideas were born in the bathroom – just ask Archimedes.
2
00:00:07,249 --> 00:00:12,599
This would come in handy for programming, but unfortunately, laptops and moisture don’t get along very well.
3
00:00:13,766 --> 00:00:16,983
But there is a surprising solution: bathroom tiles!
4
00:00:18,500 --> 00:00:24,750
We’ll picture the bathroom wall as a rectangle of width w and height h that we want to entirely fill with square tiles of size 1.
5
00:00:26,183 --> 00:00:28,650
Each tile will have 4 sides with some colors.
6
00:00:30,916 --> 00:00:35,366
For the tiling to make sense, we want the adjacent tiles’ colors to match.
7
00:00:35,366 --> 00:00:41,166
We’ll also make it so that each side of the wall has some color that again must match the tiles it’s adjacent to.
8
00:00:42,416 --> 00:00:47,416
Now say we have the colors of the wall and a finite set of tile types.
9
00:00:47,416 --> 00:00:52,416
The question is: can we create a tiling that satisfies our requirements?
10
00:00:52,416 --> 00:00:56,566
Note that we can use as many tiles of each type as we want, but we cannot rotate them.
11
00:00:58,300 --> 00:01:01,733
For this example, it is pretty clear that we can.
12
00:01:01,733 --> 00:01:09,566
However, if we were to change the top side like so, it would no longer be possible, because there are no tiles with red on the top side.
13
00:01:11,850 --> 00:01:15,100
This is essentially the programming model that we’ll be using.
14
00:01:15,100 --> 00:01:18,966
The input will be some finite sequence of colors on the top side of the wall
15
00:01:18,966 --> 00:01:22,766
(which could also be symbols to make some of the programs more readable).
16
00:01:22,766 --> 00:01:28,100
Our program will be a finite set of tile types and the remaining colors of the wall.
17
00:01:28,100 --> 00:01:33,516
Note that neither the tileset nor the wall colors can depend on the input.
18
00:01:33,516 --> 00:01:39,850
The program will accept the input if there exists a valid tiling of any non-zero height, and reject it if there’s none.
19
00:01:41,166 --> 00:01:46,733
Looking at this example, the program will accept the input, if and only if it has even length.
20
00:01:46,733 --> 00:01:52,233
It should be pretty obvious why – we have to start with the first tile and end with the second tile.
21
00:01:52,233 --> 00:01:59,366
Now notice that the tiles switched roles and we can again place the first and the second tile like so.
22
00:01:59,366 --> 00:02:06,566
Since we’re always forced to add tiles by twos for the middle colors to match, the input length must be even, else the tiling cannot exist.
23
00:02:08,366 --> 00:02:16,800
Another, slightly more advanced example is this one, where the program accepts the input, if and only if the number of ones is divisible by three.
24
00:02:16,800 --> 00:02:21,333
The idea is to count how many ones we’ve seen when tiling from the left.
25
00:02:21,333 --> 00:02:27,383
When counting, we’ll loop back to 0 when the count reaches 3, because we’re only interested in the remainder after division.
26
00:02:28,516 --> 00:02:36,100
This means that we have to end with a 0, because a remainder 0 after division happens if and only if the number is wholly divisible.
27
00:02:37,533 --> 00:02:40,316
The tiles are divided into two groups:
28
00:02:40,316 --> 00:02:44,049
we carry over the number of threes we’ve seen when the input contains a zero,
29
00:02:47,016 --> 00:02:49,416
and increment when it contains a one.
30
00:02:52,866 --> 00:02:55,750
Let’s see the tiling in action to better understand how it works.
31
00:02:57,150 --> 00:03:02,966
As you can see, the number of ones we’re carrying in the tiles correspond to the actual number when counting from the left,
32
00:03:02,966 --> 00:03:05,216
which is exactly what we want.
33
00:03:05,216 --> 00:03:10,066
Additionally, there is always exactly one tile to place at any given point in the tiling,
34
00:03:10,066 --> 00:03:12,866
since it’s uniquely determined by the previous tile and the input.
35
00:03:15,300 --> 00:03:19,950
Because there are 6 ones, which is indeed divisible by 3, the input is accepted.
36
00:03:22,266 --> 00:03:23,850
Let’s talk a bit about time complexity.
37
00:03:25,366 --> 00:03:30,233
For traditional programming models, a reasonable way to define time complexity of a problem
38
00:03:30,233 --> 00:03:35,450
is the minimum number of instructions needed to compute the solution, based on the size of the input.
39
00:03:36,283 --> 00:03:41,283
For example, bubble sort will sort an input of size n in O(n^2 ) operations,
40
00:03:41,283 --> 00:03:45,816
and binary search will find an item in a sorted array in O(log(n)) operations.
41
00:03:46,766 --> 00:03:53,366
For our programming model, this definition doesn’t make sense, since the tiling either exists or it doesn’t.
42
00:03:53,366 --> 00:03:59,550
What we’ll do here instead is measure the minimum number of rows needed to accept the input, again based on its size.
43
00:04:00,666 --> 00:04:05,883
When the input is not accepted, there will be no rows to count since the tiling doesn’t exist.
44
00:04:05,883 --> 00:04:11,049
We’ll therefore exclude rejected inputs from the calculation altogether, since there is no good way to measure them.
45
00:04:12,233 --> 00:04:17,333
But so far, we’ve only seen problems requiring exactly one row, so let’s look at one that requires a bit more.
46
00:04:19,065 --> 00:04:25,083
The task is to create a program that accepts the input, if and only if it contains parentheses that are balanced
47
00:04:25,083 --> 00:04:29,116
(meaning that for each opening one, there is a corresponding closing one to the right of it).
48
00:04:30,033 --> 00:04:32,300
One solution might look like this.
49
00:04:32,300 --> 00:04:36,883
Although daunting at first, the best way to understand it is to look at a successful tiling.
50
00:04:38,700 --> 00:04:45,349
As you can see, the tiles are defined in such a way that they connect each corresponding pair of parentheses using the wall itself.
51
00:04:45,350 --> 00:04:49,083
For example, these two parentheses are connected via this path.
52
00:04:50,316 --> 00:04:53,383
We can again separate the tiles into a few groups.
53
00:04:53,383 --> 00:04:59,316
The first two tiles just connect adjacent opening and closing parentheses, since we don’t need more than one layer for that.
54
00:05:00,316 --> 00:05:05,483
Then we have tiles for non-adjacent opening and losing parentheses, and tiles to connect them.
55
00:05:06,516 --> 00:05:09,316
Finally, we have a blank tile to fill in the gaps.
56
00:05:11,100 --> 00:05:16,266
The reason for different colors for opening and closing parentheses is that if the colors were the same,
57
00:05:16,333 --> 00:05:19,616
they would be interchangeable and the input could be unbalanced.
58
00:05:21,383 --> 00:05:25,966
As for time complexity, there can be at most n/2 pairs of parentheses
59
00:05:25,966 --> 00:05:29,583
and we need at most one row for each, so this solution runs in time O(n).
60
00:05:30,833 --> 00:05:34,416
Interestingly, this is not the fastest way this problem can be solved.
61
00:05:35,133 --> 00:05:40,016
There is an arguably more beautiful optimal solution that only requires time O(log n),
62
00:05:40,016 --> 00:05:45,433
which I’m not going to show in this video but would instead love you, the viewer, to think about on your own.
63
00:05:46,316 --> 00:05:51,966
I will leave a link to solution to this problem and many more in the description, if you’re interested in solving some of them.
64
00:05:54,316 --> 00:05:56,750
So... how strong is our model?
65
00:05:56,750 --> 00:06:00,050
Which problems can it solve and which can it not?
66
00:06:00,050 --> 00:06:04,666
Is it as strong as Python, or stronger, or is it not even close?
67
00:06:05,433 --> 00:06:10,216
Well, our model turns out to be equivalent to a linearly bounded Turing machine.
68
00:06:10,216 --> 00:06:15,816
By this we mean a non-deterministic Turing machine with a finite tape that is as long as the input.
69
00:06:16,666 --> 00:06:22,200
This means that it is not as strong as Python (and basically every other modern programming language),
70
00:06:22,200 --> 00:06:26,000
since Python is Turing complete and thus equivalent to a regular Turing machine.
71
00:06:27,183 --> 00:06:31,516
Despite this limitation, it can still solve a surprisingly large set of problems,
72
00:06:31,516 --> 00:06:33,766
like checking whether a number is prime,
73
00:06:33,766 --> 00:06:36,583
whether a maze contains a path from one point to another,
74
00:06:36,583 --> 00:06:40,266
or even whether a boolean expression has an assignment of variables that make it true.
75
00:06:41,333 --> 00:06:47,766
One neat consequence of this limitation is that there exists an algorithm to tell you, whether a given tileset will tile for a given input.
76
00:06:48,850 --> 00:06:53,850
This is not true for a regular Turing machine, where no such algorithm exists.
77
00:06:55,650 --> 00:06:58,333
Let’s extend the bathroom wall to infinity in all directions.
78
00:06:59,666 --> 00:07:05,216
The question about tiling still remains, but two new, seemingly unrelated ones arise:
79
00:07:05,216 --> 00:07:09,583
1. If a tileset can fill the plane, can it also fill it periodically?
80
00:07:09,583 --> 00:07:14,816
2. Is there an algorithm to check if a tiling exists (just as for the previous, finite model)?
81
00:07:15,700 --> 00:07:20,800
These questions, first asked by Hao Wang in the 1970, both have the sad answer “no.”
82
00:07:21,550 --> 00:07:23,866
It turns out that the first question implies the second,
83
00:07:23,866 --> 00:07:29,166
since if it were true then could just use bruteforce to look for the periodic pattern which would be the algorithm.
84
00:07:30,166 --> 00:07:34,616
However, if the second were true then this would contradict the halting problem,
85
00:07:34,616 --> 00:07:38,700
which can be proven by reducing regular Turing machines to infinite tiling programs.
86
00:07:39,400 --> 00:07:43,000
Thus, since the second is false, the first one must be false too.
87
00:07:44,100 --> 00:07:49,333
Here is an example of one such tileset that does fill the plane aperiodically, but not periodically.
88
00:07:52,666 --> 00:07:57,666
There are many other rabbit holes that I had to stop myself from going into to keep the video at a reasonable length.
89
00:07:58,816 --> 00:08:04,266
Nevertheless, I hope you enjoyed a look into this fascinating programming model and who knows,
90
00:08:04,266 --> 00:08:07,250
maybe we’ll all be programming in T++ some time in the future.