Tiling
Contents
Tiling¶
In this notebook we prove the undecidability of the tiling problem.
Recall that in this problem we are given a finite pointed tile set \(\mathcal{T}\), and the problem is to determine whether there is a proper tiling of the first quadrant of the plane using \(\mathcal{T}\). A tile is a square with colors on the four sides. The colors can be anything, of course.
The main problem is whether, given a tile set \(\TT\), we we can tile the first quadrant of the plane in such a way that \(t_0\) goes on the corner, and matching edges have the same color. This is what we mean by a proper tiling of the first quadrant.
A finite, pointed tile set \((\TT,t_0)\) is a finite set \(\TT\) of tiles with a fixed distinguished tile \(t_0\in\TT\). When we talk about tile sets we always will mean a finite, pointed tile set.
Notation
Let \(\mathbb{T}\) be the set of (codes of) all finite pointed tile sets. Let \(\Tile\) be the set of (codes of) tile sets \(\TT\) with the property that the the first quadrant can be properly tiled with \(\TT\).
In our work, we are interested in programs \(p\) with the following features:
(a) \(p\) is tidy.
(b) \(p\) only uses register 1.
Let \(A\) be the set of programs with those two properties, and let \(B\subseteq A\) be the subset with the additional property that \(\phifn_p(\ )\dar\). Then \(A\) is decidable (easily) and we have shown that \(B\) is is undecidable.
Theorem 4
There is a total computable function \(\TT: A\to \mathbb{T}\) such that
Thus, \(B\) is undecidable.
Our goal
A computable and total function \(\TT: A\to \mathbb{T}\) such that \(p\notin B\) \(\Leftrightarrow\) \(\TT(p)\) can tile the quadrant.
The definition of \(\TT(p)\)¶
This section gives the details on the function \(\TT\). 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.)
Warning
Further, we have an issue with the numeral \(1\) and the \(\one\hash\) symbol \(\one\). In order to not avoid a potential confusion, we use two fonts. The symbol \(1\) is used for the line number in a program, and the symbol \(\one\) is used for the symbol which we put in the registers of our machine.
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 \(\TT(p)\) for \(p\in A\). Fix such a program \(p\).
We start with 18 tiles that are part of \(\TT(p)\) for all \(p\in A\).
The rest of \(\TT(p)\) depends on the program \(p\). To begin, when instruction \(i\) of \(p\) is \(\one\hash\), we include the tile
And when instruction \(i\) of \(p\) is \(\one\hash\hash\), we include the tile
When instruction \(i\) is \(\one^m\hash\hash\hash\) we include
When instruction \(i\) is \(\one^m\hash\hash\hash\hash\) we include
Finally, when instruction \(i\) is the cases instruction \(\one\hash\hash\hash\hash\hash\), we include the three tiles
Notice that \(\TT(p)\) is a finite set of tiles. We also want \(\TT(p)\) to be pointed, and we take the green tile above.
This completes the definition of the function \(\TT\). It’s clear that \(\TT\) 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 \(\TT(p)\).
Example
When \(p\) is the program \(\one\hash\one\hash\hash\hash\hash\),
\(\TT(p)\) would have the 18 tiles that come for free, and also the two tiles below:
In these two tiles, the symbol \(1\) is the first line number of \(p\),
not the \(\one\hash\) symbol \(\one\).
Here is a finite part of a tiling of the first quadrant with \(\TT(\one\hash\one\hash\hash\hash\hash)\):
The rest of our work is devoted to showing that if there is a tiling of the quadrant with \(\TT(p)\), then \(\phifn_p(\ )\dar\).
Some observations¶
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.
An easy induction shows the following: in a tiling of the first quadrant that starts with the starting tile, every row has to have all blanks after some finite point.
Tip
It would be good to prove this.
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.
If \(p\) has \(n\) instructions, then there is no tile with \(n+1\) on the bottom. Thus no complete tiling of the first quadrant can have a tile where \(n+1\) appears on the top.
Restatement of our goal
\(p\) runs forever (on all empty registers) if and only if \(\TT(p)\) can tile the first quadrant.
\(p\) halts (on all empty registers) if and only if \(\TT(p)\) cannot tile the first quadrant.
Definition 6
The word encoded in row \(n\) is the word composed of all symbols on the tops of the tiles in row \(n\) after the instruction tile (the first tile in row \(n\)).
Example
This shows part a tiling, together with the words encoded in the first four rows (on the right).
Let \(p\) be a program.
Suppose that row 67 of a tiling using \(\TT(p)\) is
and that instruction 131 of \(p\) is \(\one^8\hash\hash\hash\).
In view of the fact that 131 + 8 = 139,
the instruction tile in the first column of row \(68\) is
Thus, row 68 must be the top row below:
The point
The word encoded in row 68 is \(\one\hash\hash\one\). This is exactly the same as the word encoded in row 67.
Don’t read the symbol as “copyright” but as “copy right.”
A similar remark applies for instructions in \(p\) which are back-transfers \(\one^k\hash^4\).
We continue with facts along the same lines for the instructions
\(\one\hash\) and \(\one\hash\hash\). Since the lines of argument are similar, we only discuss the second of these.
Suppose that row 4743 of some tiling of the quadrant starts out
and instruction 24 of the program is \(\one\hash\hash\). Then the first tile in row 4744 must be
What are the next tiles in row 4744?
Click for the answer.
The word encoded in row 4744 is 1##1#. This is exactly the word encoded in row 4743, with # added at the end.
This shows that we have implemented the 1## instructions correctly.
Finally, let’s get one last parallel fact, this time for the case instruction. Suppose again that row 4743 of some tiling of the quadrant starts out
But now uppose that line 24 of the program is the case instruction \(\one\hash\hash\hash\hash\hash\).
Then the first tile in row 25 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 \(\one\), \(\hash\), 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 \(\one\)s:
We now know the last tiles before the blank tiles in row 4744:
Indeed, the whole row has to be
The word encoded in row 4744 is \(\hash\hash\one\).
This is exactly the word encoded in row 4743, with the first symbol (a \(\one\)) deleted.
And the instruction to go to is 26 = 24 + 2. So we have implemented \(\one\hash^5\) correctly, at least in the case when register \(1\) starts with a \(\one\).
Formal statement¶
Fix \(p\in A\), and consider \(\TT(p)\) and also the run of \(p\) with nothing in any register.
For all \(s\), exactly one of the following two things happen.
(a) The program halts in \(\leq s\) steps, and there is no tiling of the first \(s\) rows of the plane (starting with \(s = 0\)).
(b) The program runs for at least \(n\) steps, and there is a unique tiling of the first \(n\) rows. And in this case, for \(k \leq n\) the top edge of the \(k\)th row has the line number to be executed in step \(k+1\) (or \(n+1\) if the program halts at step \(k\)) then the contents of the register, symbol-by-symbol, and then all blanks.
The converse¶
We conclude our work on tiling by showing that \(\Tile \leq_m \overline{K}_{empty}\). Given a pointed tile set \(\TT\), make a program \(f(\TT)\) such that running \(f(\TT)\) on all empty registers using the \(\mu\)-operator to look for some number \(n\) such that \(\TT\) cannot tile the \(n\times n\) square containing the corner.
(If there is no such \(n\), the program goes on looking forever.)
If \(\TT\) has a tiling, the program \(f(\TT)\) never halts. So \(f(\TT)\in \overline{B}\).
And (crucially) if \(\TT\) has no tiling of the whole quadrant, then by an argument using the Koenig Infinity Lemma, there is some \(n\) such that \(\TT\) cannot tile the \(n\times n\) square containing the corner.
In this case \(\semantics{f(\TT)}(\ )\downarrow\).
Exercise 43
In our work on tiling, we took a program \(p\) with \(n\) lines and defined \(\TT(p)\) with \(n+9\) colors. Is it possible to change the mapping \(\TT\) to only use a fixed finite set of colors?
Exercise 44
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 \(\TT\) and four elements of it called \(NE\), \(NW\), \(SE\), and \(SW\). A finite rectangle is tiled by \(\TT\) 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.
The tiling problem in this paper, and in most of the work in the area, is for tiling the whole plane. What we did is to consider the first quadrant and pointed tile sets. So our undecidability result is much easier than the more well-known tiling problem. That problem 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.