Tiling#
Early on, we mentioned some algorithmic probles related to tiling. Here is a quick review.
A tile is a square with colors on the four sides. The colors can be anything, of course. A finite, pointed tile set \((\mathcal{T},t_0)\) is a finite set \(\mathcal{T}\) of tiles with a fixed distinguished tile \(t_0\in\mathcal{T}\).
Notation
Let \(\mathbb{T}\) be the set of (codes of) all finite pointed tile sets \((\mathcal{T},t_0)\). Let \(K^{\mathbb{T}}\) be the set of (codes of) tile sets \(\mathcal{T}\) with the property that there is a proper tiling of the first quadrant with \(\mathcal{T}\). (Proper here means that \(t_0\) goes in the bottom-left corner, and all neighboring edges of tiles have the same color.)
When we talk about tile sets in this section, we always will mean a finite, pointed tile set. And when we talk about a tiling, we always mean a proper tiling.
The complement set \(\overline{K}^{\mathbb{T}}\) is the set of (codes of) tile sets \(\mathcal{T}\) with the property that the the first quadrant cannot be properly tiled with \(\mathcal{T}\).
Our goal
Clearly \(A\) is decidable, and it is easy to see that \(K^1\) is undecidable.
Theorem 14
\(\overline{K}^1\leq_m {K}^{\mathbb{T}}\). Equivalently, \(\overline{K}^1 \leq_m K^{\mathbb{T}}\).
That is, there is a total computable function \(\mathcal{T}: A\to \mathbb{T}\) such that
That is, \(\mathcal{T}(p)\) can tile the quadrant if and only if \([\![p]\!](\ )\!\!\uparrow\).
As a result, \(\overline{K}^{\mathbb{T}}\) is undecidable. So \({K}^{\mathbb{T}}\) is also undecidable.
Preparation#
Let \(p\) be a tidy program. As we saw in Proposition 4, we can computably find a program \(q\) with the following properties:
\([\![p]\!](\ )\!\!\downarrow\) if and only if \([\![q]\!](\ )\!\!\downarrow\)
The only register mentioned in \(q\) is R1.
Assumption
We are going to replace \(p\) by \(q\). That is, we assume from now on that the only register mentioned in \(p\) is R1.
Ideas behind the construction#
Let \(p\) be a program that only uses R1. In the case that \([\![p]\!](\ )\!\!\uparrow\), we want a run of \(p\) to give rise to a tiling of the entire quadrant. The idea is that the rows of the tiling should look like the contents of the register step-by-step. Moreover, we would like the leftmost entry in each row to encode the instruction number that is being executed. If \(p\) is tidy, then the run of \(p\) on empty registers takes infinitely many steps. We do not have \([\![p]\!](\ )\!\!\uparrow\) merely due a bad transfer instruction. So the run will correspond to the tiling of the entire quadrant. And if \([\![p]\!](\ )\!\!\downarrow\), there will not be such a tiling; the fact that the computation halted will preclude a tiling of the quadrant.
Here is an example which we shall mention at several points in the rest of this discussion. We take \(p\) to be the program 1#1##11####. Clearly \([\![p]\!](\ )\!\!\uparrow\). We want the bottom 8 rows of the tiling of the quadrant to resemble
We say resemble here because what is shown above is not a set of tiles in the first place: there are no colors on the edges. But our details below are an elaboration of this idea. It might be fun for you to work out your own elaboration at this point before looking below. But if you want to see how our definitions will work, you can look at Example 1.
Warning
We have an issue with the numeral \(1\) and the 1# symbol 1. In order to avoid a potential confusion, we
use two fonts. The symbol \(1\) is used for the line number in a program, and the symbol 1 is used for the symbol which we put in the registers of our machine.
The definition of \(\mathcal{T}(p)\)#
This section gives the details on the function \(\mathcal{T}\). Before we present it, we need a comment on the set of color which we are going to use. In our earlier work on tiling,
we saw tiles whose sides had actual colors, such as the eight tiles below
Here, we are going to make a change. For a given program \(p\), we are going to need \(8 + (n+1)= n + 9\) colors. Since our eyes can only reliably distinguish a (small) finite number of colors, we are going to use numbers as some of our colors. (Recall that the “colors” can be anything.)
We are going to use line numbers in \(p\) as colors, and so if \(p\) has \(n\) lines, we want \(1\), \(\ldots\), \(n\) as colors. We also want \(n+1\), since if \(p\) halts we want to think of the control as on “line \(n+1\)”. We also are going to use as symbols the \(\one\hash\) symbols \(\one\) and \(\hash\), the card symbols \(\heartsuit\) and \(\diamondsuit\) (we use these just as a way to add a color to this page), an oblong rectangle, the copyright symbol (a circle with the letter C inside), the word “start”, and a blank color (where the side of a square is just left blank).
We need only worry about defining \(\mathcal{T}(p)\) for \(p\in A\). Fix such a program \(p\).
We start with 18 tiles that are part of \(\mathcal{T}(p)\) for all \(p\in A\).
The rest of \(\mathcal{T}(p)\) depends on the program \(p\). To begin, when instruction \(i\) of \(p\) is 1#, we include the tile
And when instruction \(i\) of \(p\) is 1##, we include the tile
When instruction \(i\) is 1\({}^m\)### we include the two tiles
When instruction \(i\) is 1\({}^m\)#### we include the two tiles
Finally, when instruction \(i\) is the cases instruction 1#####,
we include the three tiles
Notice that \(\mathcal{T}(p)\) is a finite set of tiles. We also want \(\mathcal{T}(p)\) to be pointed, and we take the green tile above.
This completes the definition of the function \(\mathcal{T}\). It’s clear that \(\mathcal{T}\) is total and computable. The easy part of our result is showing that if \(p\in A\) halts, then there is a propert tiling of the quadrant with \(\mathcal{T}(p)\).
Example 1
Let \(p\) be our running example program 1#1##11####.
\(\TT(p)\) contains the 18 tiles that come for free, and also the three tiles below:
In these two tiles, the symbol \(1\) is the first line number of \(p\),
not the 1# symbol 1.
Here is a finite part of a tiling of the first quadrant with \(\mathcal{T}(p)\):
Some observations#
We continue with some observations which are used in verifying that our construction works. These will be used in Lemma 4 below. Fix a program \(p\), and consider \(\mathcal{T}(p)\).
The only tile with a blank on the left is the all blank tile. Thus, if one of the tiles in a given row has a blank on the right, then forever to its right, all the tiles are blank.
If the copyright symbol appears on the east or west edge of a tile, then all tiles in that row must have either the copyright symbol or blank on their east and west.
Same with the heart symbol: if it occurs on the east or west side of a tile, then all tiles in that row must have either the heart symbol or blank on their east and west.
And the same for the diamond symbol as well.
A tile has one of the line number symbols (the number 1, 2, \(\ldots\), n, n+1) on the top if and only if that tile is in the first column. We call these instruction tiles. The instruction tiles are the only ones with the oblong rectangle on the left side.
We are going to denote by \(k\) the number of instructions in \(p\). Notice that there is no tile with \(k+1\) on the bottom.
Tip
Consider a tiling of two neighboring rows of the quadrant, say row \(i\) and row \(i+1\). Suppose that the first blank in row \(i\) is the \(j\)th tile. Then the first blank in row \(i+1\) is either the \((j-1)\)st tile, or the \(j\)th tile, or the \((j+1)\)st tile. An easy induction then shows the following: in a tiling of the first quadrant or of some finite number of rows at the bottom, every row has to have all blanks after some finite point.
We don’t actually need to know this fact, but it would be good to prove this.
Definition 21
The word encoded in rows \(n\) is the word composed of all symbols on the tops of the tiles in row \(n\) from the bottom, starting after the instruction tile (the first tile in row \(n\)).
Example 2
Again we take \(p\) to be our example program 1#1##11####.
We see part a tiling (the bottom four rows), together with the words encoded in those rows, shown on the right.
Main lemma#
Before we state our main lemma, we need some terminology about the rows in a tiling and about the step numbers in the run of a program. We start counting the rows with row \(0\). (So in a tiling of the quadrant the first tile in row \(0\) is the start tile.)
For a program \(p\), “step 0” gets us ready before step \(1\). In step \(1\), we execute the first instruction of \(p\). In each step \(n\), we execute instruction \(i(n)\), and we also calculate the next instruction to execute, \(i(n+1)\). We always have \(0\leq i(n)\leq k+1\), where \(k\) is the number of instructions in \(p\).
For example, let \(p\) be the program 1#1##11####.
We have \(i(0) = 0\), \(i(1) = 1\), \(i(2) = 2\), \(i(3) = 3\), \(i(4) = 1\), \(i(5) = 2\), \(\ldots\).
For another, let \(q\) be 1#1##. Then \(i(0)= 0\), \(i(1) = 1\), \(i(2) = 3\). The number of instructions in \(q\) is \(k =2\),
and so \(i(2) = k+1\).
Lemma 4
Fix \(p\in A\), and consider \(\mathcal{T}(p)\) and also the run of \(p\) on empty registers.
For all \(n\) the following are equivalent:
The run goes on for at least \(n\) steps without halting.
There is a (unique) tiling of the first \(n\) rows. The \(n\)th row starts with an instruction tile bearing \(i(n)\) on the bottom and \(i(n+1)\) on the top, and the the word encoded in the \(n\)th row is the contents of the register after \(n\) steps.
We prove this lemma by induction on \(n\). For \(n = 0\), both statements are true. The unique tiling of row \(0\) is the starting tile followed by all blanks.
All of the work is in verifying the induction step. So assume the equivalence of 1 and 2 for \(n\); we prove it for \(n+1\).
First, assume that \(p\) does not run for at least \(n+1\) steps. Then either it does not run for at least \(n\) steps, or else it does run for at least \(n\) steps, and then halts on step \(n+1\). In the first case, by induction hypothesis, there is no tiling of the first \(n\) rows. So there is no tiling of the first \(n+1\) rows, either. In the second case, the instruction tile in row \(n\) has \(k+1\) on the top row. In this case, there is no way to continue the tiling, because there is no tile with \(k+1\) on the bottom. So there is no tiling of the first \(n+1\) rows.
Turning things around, we have shown that (2) for \(n+1\) implies (1) for \(n+1\).
Second, assume (1) for \(n+1\): \(p\) does run for at least \(n+1\) steps. Then it runs for at least \(n\) steps. This is point (1) for \(n\). By the induction hypothesis, we have (2) for \(n\). So we have a unique tiling of the first \(n\) rows, and the word encoded in row \(n\) is the contents of the register after \(n\) steps of \(p\). We need to see that we have a unique tiling of row \(n+1\), and that the word encoded in row \(n+1\) is the contents of the register after \(n+1\) steps.
Consider the instruction tile in row \(n\). By induction hypothesis, the number at the bottom of this tile is \(i(n)\), and the number at the top is \(i(n+1)\). Now \(i(n+1)\) cannot be \(k+1\), where \(k\) is the number of instructions in \(p\). For if \(i(n+1) = k+1\), the program \(p\) could not run for \(n+1\) steps. So \(1\leq i(n+1)\leq k\).
At this point the proof splits into cases depending on what instruction \(i(n+1)\) of \(p\) is.
Case 1: Instruction \(i(n+1)\) of \(p\) is 1#. This is very similar to Case 2 just below.
Case 2: Instruction \(i(n+1)\) of \(p\) is 1##.
Details here
For the sake of exposition we work an example rather than the general case.
Let \(n = 4743\). Suppose that row 4743 of the tiling starts out
and instruction 24 of the program is 1##. We check that there is a unique way to tile row 4744.
The first tile in that row must be
This is because the only tile in \(\mathcal{T}(p)\) with \(24\) on the bottom is the tile above.
What are the next tiles in row 4744?
Click for the answer.
Of course, it must be checked that this really is the only way to tile row 4744. The observations made above should help you do this.
So we see that there is a unique way to tile row 4744. Recall that we are verifying point (2) for \(n+1\). It remains to
show that the word encoded in the register after \(n+1\) steps is is the contents of the register after \(n+1\) steps.
By what we saw above, the contents of the register after \(n\) steps is 1##1. Step \(n+1\) executed the instruction 1##.
And so the contents after \(n+1\) steps is 1###1#. This is exactly the word encoded in row 4744.
This verifies point (2) for \(n+1\). Of course, we only worked with an example, but the general case is an elaboration of what we showed here.
Case 3(a): Instruction \(i(n+1)\) of \(p\) is 1^m ### and R1 is not empty after executing \(n\) steps of \(p\).
Details here
To make things concrete, suppose that \(n = 67\), \(i(68) = 131\), \(m=8\), that row \(n\) of the tiling is
and that instruction 131 of \(p\) is 1\({}^8\)###. Thus, \(i(69) = 131 + 8=169\).
We have two options for the instruction tile in row \(68\).
We claim that this tile must be
It is important to check that the instruction tile in row \(68\) cannot be the same tile but with the copyright symbol replaced by the blank.
We claim that row \(68\) must be the top row below:
We mainly leave this verification to you. The tiles in row \(68\) must either be blank or involve the copyright symbol, and a case-by-case analysis shows that row 68 must be as above.
The word encoded in row \(67\) is 1##. By our induction hypothesis on \(n = 67\),
This is exactly the same as the same as the contents of the register after \(67\) steps. Instruction 68 of \(p\) was
1^8 #^3. After executing that instruction, the register did not change. So it still is 1##. All of this verifies
(2) for \(n+1\) in Case 3(a).
Don’t read the symbol as “copyright” but as “copy right.”
Case 3(b): Instruction \(i(n+1)\) of \(p\) is 1^m ### and R1 is empty after executing \(n\) steps of \(p\).
Details here
This is very much like Case 3(a) above, with one important change. The instruction tile in row \(n+1\) now must be the tile with a blank on the right side.
The rest of the details are as in in Case 3(a).
Case 4(a): Instruction \(i(n+1)\) of \(p\) is 1^m #### and R1 is not empty after executing \(n\) steps of \(p\).
Of course, this is similar to Case 3(a).
Case 4(b): Instruction \(i(n+1)\) of \(p\) is 1^m #### and R1 is empty after executing \(n\) steps of \(p\).
This is similar to Case 3(b).
Case 5: Instruction \(i(n+1)\) of \(p\) is 1#####.
Details here
Suppose again that \(n = 4743\) and that row 4743 of some tiling of the quadrant has the encoded word 1##1. For example, it might be
So \(i(4744) = 24\). We are assuming
that instruction 24 of the program is the case instruction 1#####.
Then the first tile in instruction 4744 can be any of the three tiles
So the situation is
We cannot have the symbol above the blank to be as below
This is because the symbols in the middle of row 4744 have to be
1, #, or ``blank.’’ So there would be no way to match the heart symbol at the end.
We must have all blanks on the far right, and then next to that a tiles with two 1s:
We now know the last tiles before the blank tiles in row 4744:
Indeed, the whole row has to be
An important detail here is that the only instruction tile with 24 on the bottom and 1 on the right has 26 on the top.
By our induction hypothesis on \(n\), the word encoded in row 4743
is the contents of the register after 4743 steps.
The word encoded in row 4744 is ##1.
This is exactly
the word encoded in row 4743, with the first symbol (a 1) deleted. So, this is the contents of the register after 4744 steps.
To verify point (2) for \(n+1\), we only need to check the point about the top of the instruction tile in row 4744. We have seen that
step 4744 executed a case instruction and step 4744 of the execution of \(p\) was for the instruction 1#####.
Since this starts with a 1, the next instruction to execute is 24 + 2 = 26. That is, \(i(n+1) = 26\).
All of this verifies point (2) for \(n+1\),
but only in the case when the word encoded in row 4743 starts with a 1.
Similar work applies when the word encoded in row 4743 starts with a #.
Now what happens when the word encoded in row 4743 is the empty word? By induction hypothesis, after 4743 steps of running \(p\), the register is empty. Moreove, the first tile in row 4744 must be the first of our three options, shown again below:
By trying things out again, we see that the rest of row 4744 must be copies of the empty tile. So the word encoded in that register is again empty.
Note also that \(i(4744) = 25 = 24+1\). This all corresponds to executing the 1##### instruction on the empty register.
We have verified all parts of (2) for \(n+1\).
Proof of the theorem#
Lemma 4 leads to the proof of the main result in this section, Theorem 14.
We now turn to the proof.
Reminder of what we are proving.
If \(p\) runs forever (on all empty registers), then \(\mathcal{T}(p)\) can tile the first quadrant.
If \(p\) halts (on all empty registers) at some point, then \(\mathcal{T}(p)\) cannot tile the first quadrant.
For the first statement, the lemma implies that for all \(n\), there is a unique tiling of the first \(n\) rows of the quadrant. From the uniqueness, if \(n < m\), then the tiling of the first \(n\) rows has to be a restriction of the tiling of the first \(m\) rows. It follows that we can take the union over \(n\) of the tiling of the first \(n\) rows. This will be a tiling of the entire quadrant.
For the second statement, suppose towards a contradiction that the run of \(p\) halts in \(n+1\) steps and yet \(\TT(p)\) can tile the quadrant. We use Lemma 4. We have (1) for \(n\), and so we have (2) for \(n\) as well. Let \(k\) be the number of instructions in our program \(p\). The instruction tile in row \(n\) (the first tile) must have \(k+1\) on the top; this is what it means for the run to halt in \(n+1\) steps. Let us call this tile \(t^*\). Since we have a tiling of the entire quadrant, there must be a tile on top of \(t^*\). But no tile in our tile set \(\mathcal{T}(p)\) has \(k+1\) on the bottom. This is the contradiction.
The reverse inequality#
Theorem 15
\( {K}^{\mathbb{T}}\leq \overline{K}^1 \).
That is, there is a total computable function \(f: \mathbb{T}\to A\) such that
That is, \(\mathcal{T}\) can tile the entire quadrant if and only if \(f(\mathcal{T})\) does not halt.
In other words, \(\mathcal{T}\) cannot tile the entire quadrant if and only if \(f(\mathcal{T})\) does halt.
The work here is based on an important mathematical result.
Lemma 5 (Konig Infinity Lemma)
Every infinite tree \(T\) which is finitely branching has an infinite branch.
Proof. We construct a sequence \(t_n\) of points in \(T\) by recursion. Each \(t_n\) will have distance \(n\) from the root of \(T\). Let \(t_0\) be the root. Given \(t_n\), consider the set \(C\) of children of this node. This is a finite set. The set of nodes of \(T\) whose distance to the root is \(\leq n\) is finite, since \(T\) is finitely branching. So the set \(D\) of nodes whose distance is \(> n\) is infinite. There must be some \(u\in C\) which is an ancestor of infinitely many elements of \(D\). Let \(t_{n+1}\) be any such node \(u\).
This very general result has as a special case the following fact:
Lemma 6
If a tile set \(\mathcal{T}\) cannot tile the entire quadrant, then there is some natural number \(n\) such that \(\mathcal{T}\) cannot tile the \(n\times n\) square in the lower left corner.
Proof. We show the contrapositive. Assume that for all \(n\) there is a tiling using \(\mathcal{T}\) of the \(n\times n\) square in the corner. We show that there is a tiling of the entire quadrant.
Consider the set of all tilings of all \(n\times n\) squares in the corner. It is a tree, where the “edge” relation
relates a tiling of the \(n\times n\) square to a tiling of the \((n+1)\times (n+1)\) square iff the first is a restriction of the second.
This is tree: the root is the empty tiling of the \(0\times 0\) square. It is finitely branching, since the tile set \(\mathcal{T}\) is finite to begin with. By Lemma 5, the tree has an infinite branch.
By taking the union of the tilings along this branch, we tile the entire quadrant.
(One cannot in general take the union of tilings, since those tilings might conflict. But if we have a branch in this tree, then the tilings along the branch agree on their common squares. And in this case, we can take the union.)
We turn this observation into the proof of Theorem 15.
Given a pointed tile set \(\mathcal{T}\), make a program \(f(\mathcal{T})\) such that running \(f(\mathcal{T})\) on all empty registers using the \(\mu\)-operator to look for some number \(n\) such that \(\mathcal{T}\) cannot tile the \(n\times n\) square containing the corner.
(If there is no such \(n\), the program goes on looking forever.)
The point again is that if \(\mathcal{T}\) has no tiling of the whole quadrant, then our last lemma shows that \([\![f(\mathcal{T})]\!](\ )\!\!\downarrow\).
Exercise 73
Our work on tiling dealt with finite tile sets. This problem relaxes the finiteness requirement. Construct an infinite pointed tile set \(\mathcal{T}\) with the following properties:
\(\mathcal{T}\) is computable.
For all \(n\), \(\mathcal{T}\) can tile the \(n\times n\) square in the lower-left corner.
There is no tiling of the entire quadrant using \(\mathcal{T}\).
Exercise 74
In our work on tiling, we took a program \(p\) with \(n\) lines and defined \(\mathcal{T}(p)\) with \(n+9\) colors. Is it possible to change the mapping \(\mathcal{T}\) to only use a fixed finite set of colors?
Exercise 75
In this problem we consider a variant of the tiling problem where the goal is not to tile the entire first quadrant but rather to tile a finite rectangle in a noteworthy way.
A four-pointed tile set is a tile set \(\mathcal{T}\) and four elements of it called \(NE\), \(NW\), \(SE\), and \(SW\). A finite rectangle is tiled by \(\mathcal{T}\) if there is a tiling in the usual sense with the property that its northwest corner is tiled by \(NW\), its northeast corner is tiled by \(NE\), etc.
Show that the problem of determining whether a four-pointed tile set has a rectangle which is tiled by it is undecidable.
Credits
The original source on tiling is Hao Wang’s paper from 1961 entitled “Proving theorems by pattern recognition—II”, Bell System Technical Journal, 40 (1): 1–41. This paper has the undecidability of tiling a pointed tile set. It was for tiling the entire plane rather than the quadrant. It also employed the undecidability of the halting problem for Turing machines rather than for register machines. The work there is a bit easier than what we do here. Put another way, if one were to prove that Turing machines can emulate register machines, the details would be similar to what we did concerning the instructions of the form 1#, 1##, or 1#####.
It is more interesting and much more difficult to study the tiling problem on tile sets that do not come with a “start tile” \(t_0\). The tiling problem for finite tile sets was shown to be undecidable by Raphael Robinson in his paper “Undecidability and Nonperiodicity for Tilings of the Plane,” Inventiones Mathematicae, 12(3), 1971 pp. 177–209. There are newer and simpler proofs of this result as well.