5.6 Undecidable Problems 279
Figure 5.6: The problem TILING (cl,... , c4 denote four colors of tile to).
Show that the problem TILING is undecidable. [Hint: Encode the Turing
machine configurations by colors so that the colors of each row in the
first quadrant represents one configuration, and the change of colors
from one row to the next follows the instructions of a Turing machine.]