Chapter 5: Two Dimensions and Beyond

Section 7: Systems Based on Constraints

Undecidability [for 2D constraints]

The general problem of whether an infinite pattern exists that satisfies a particular constraint is formally undecidable (see page 1139). This means that in general there can be no upper bound on the size of region for which the constraints can be satisfied, even if they are not satisfiable for the complete infinite grid.

From Stephen Wolfram: A New Kind of Science [citation]