Neighborhood dominoes

Suppose that the neighborhoods of an automaton were split into several parts (typically, overlapping) which were used to construct tiles - dominoes if the sequence were linear. The fundamental problem is tiling the configuration space, ensuring that the states of the cells always coincide wherever the tiles overlap; a triviality in one dimension, but not always soluble for higher dimensions.

Suppose further that some of the tiles were withdrawn from the game; for instance those forming neighborhoods whose evolution did not proceed as desired, maybe tiles whose central cell changed between generations. Can large designs be constructed from the remaining tiles? And if so, how can they be described?

Evidently this procedure reveals configurations having periodic evolution, or consisting in periodic displacement. The longer the period, the larger the neighborhood required; each one requires enough internal information to guide its own evolution the necessary number of steps.

To avoid the possibility of an undecidable tiling in two or more dimensions, the search can be confined to configurations of a fixed spatial periodicity in all but the last dimension. The first step is to catalogue the tiles which can be strung out along a single direction, noting all the pairs which can be joined together.

---

Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx