Return to Revisions

The Tiling problem is undecidable. This is the problem, given a finite set of tile types, to determine whether there is an arrangement of them with adjacent sides matching that tiles the plane. The problem is undecidable because the Halting problem for Turing machines reduces to it, in the sense that every Turing machine program corresponds to a tiling problem, which has a tiling if and only if the program fails to halt. Basically, the run of the machine is encoded into the tiling, which can continue as long as the program keeps running.