Puzzle 3

A weak tiling system is a quadruple ${\mathcal D} = (D,D_0,H,V)$ where $D$ is a finite set, $D_0 \subseteq D$ and $H,V \subseteq D \times D$. A {\em tiling\/} by ${\mathcal D}$ is a function $f : \Nat \times \Nat \to D$ such that the following hold:
$f(m,0) \in D_0$ for all $m \in \Nat$.
$(f(n,m),f(n{+1},m)) \in H$ for all $m,n \in \Nat$.
$(f(n,m),f(n,m{+1})) \in V$ for all $m,n \in \Nat$.
Show that it is undecidable whether there exists a tiling by a weak tiling system.

(Normally, a tiling system is specified as a quadruple ${\mathcal D} = (D,d_0,H,V)$, where $D$, $H$ and $V$ are as above and $d_0 \in D$. A tiling $f$ by such a system ${\mathcal D}$ must satisfy $f(0,0) = d_0$. In the puzzle, the constraint at the origin is replaced by a weak constraint for the bottom row of the tiling. Notice that the weak constraint does not insist that all tiles from $D_0$ be used on the bottom row.)

A Solution Sketch

Recall the standard way in which the standard tiling problem is shown to be undecidable. The halting problem for Turing machines starting with blank tape is reduced to tiling. The tiles are so designed that row $i$ in the tiled plane contains the configuration of the Turing machine at time $i$. Each tile holds one cell of the Turing machine tape, and additionally maybe a state and/or left-right endmarkers and extra signals to indicate whether the head is moving left/right. If the machine halts or hangs at time $i$, then the tiling cannot be extended beyong row $i$. We assume without loss of generality that at any step, the Turing machine either rewrites the symbol on the scanned square or moves its head one square left/right, but not both. We also assume that the Turing machine never hangs (falls off the left end)---it either halts, or moves forever.

In this puzzle, we can only specify what tiles are to be used in the first row. We will use a similar reduction---given a Turing machine $M$, to decide whether it halts when started on blank tape, we design a tiling system with the new constraints. A major difference is that each row now contains infinite copies of the configuration of $M$ at the corresponding time.

Let the configuration be described by a string as follows:

L a b q c B B B R
L and R are left and right endmarkers (represented in the tiling, not present on the tape), B is the blank symbol, q is the state of the machine. In a departure from convention, we allow the configuration to contain some trailing blanks beyond the rightmost used symbol as well, as long as this number of blanks is finite.

The tiles contain one square each of the tape. In addition, the tile representing the extreme left/right square of the configuration also has the endmarker L or R , and the tile containing the scanned square has the state as well. A tile containing just B is called a passive tile. The configuration at time 0 is represented by the single tile containing L, q_0, B, R . This is the only tile in $D_0$; thus the first row of the tiling contains the initial configuration of $M$ repeated infinitely often.

Let the plane be tiled upto row $i$, and let row $i$ contain copies of the configuration at time $i$, each copy using $s$ tiles. The next row is tiled as follows. If $M$ changes a scanned symbol, this change can be propagated to the tiles of the next row as in the standard case. So row $i{+1}$ also contains the same number of copies of the new configuration, each of size $s$. If $M$ makes a left/right move without crossing the extreme squares in the represented configuration, again the change can be propagated to the next row.

If $M$ makes a right move, and the tape head is already in the rightmost sqaure of the configuration, then we need to extend the size of each configuration. We allow two tiles to be placed on top of each tile containing a state and an R endmarker and requiring a right move $(q,a,R)$, where $\delta(q,a) = (p,R)$. One tile has the letter \texttt{a}, no right endmarker, and a special signal signifying 2z``propagate''; the other has a B , a right endmarker R , and a special signal ``kill''. For all other tiles, we allow at any stage three types of tiles to be placed above: one is the tile $T$ that would be allowed in the standard reduction, another is the tile $T$ with an additional signal ``propagate'', and the third is a passive tile with the ``kill'' signal. The horizontal rules are as follows: adjacent tiles must both have ``propagate'' or both have ``kill'' or both have neither signal, except at L / R boundaries. At these boundaries, a kill/propagate signal, if present, must toggle.

The effect of these horizontal rules is that if we place a propagate tile above the right cell of a copy of the configuration, then all tiles in this copy of the configuration must be of type propagate, all tiles in copies on either side must be of type kill, all tiles in the copies beyond those must be of type propagate and so on. That is, alternate copies of the configuration will be of type propagate and type kill. A kill configuration kills itself and lets its tiles become passive to be used as extra space for the previous configuration. A propagate configuration stays alive and uses extra space from its right neighbour. So at the next time step, there will be half the number of copies of the new configuration, and each copy will be twice the size.

The propagate signal must carry some more information too at the R boundary. Since the tape head is moving right, the state of $M$ must now be written in the right neighbour (in a newly acquired passive neighbour). The horizontal rules can take care of this too.

The remaining design is exactly as in the standard case. So the set of tiles and the horizontal/vertical rules can be designed in an analogous fashion, with extra rules to account for the kill/propagate constraints. The details are left to the interested reader.

Meena Mahajan, IMSc, Chennai
meena@imsc.ernet.in