## Tilings and undecidability in cellular automata

Department of Mathematics

University of Turku

Wednesday, 1 September 2010, 14:00 (note the unusual weekday)

Cybernetica Bldg (Akadeemia tee 21), room B101

Slides from the talk [pdf]

**Abstract**: Wang tiles are unit square tiles with colored
edges. In valid tilings of the plane neighboring tiles are required to
have identical colors on the adjacent edges. The tiling problem (aka
the domino problem) is the algorithmic question to decide if it is
possible to tile the infinite plane with copies of a given finite
collection of Wang tiles. This question is well known to be
undecidable (Berger, 1963).

In this talk we discuss algorithmic questions related to cellular
automata (CA). We show that many questions can be proved undecidable
using a reduction from the tiling problem, or some variants of the
tiling problem. Questions discussed include nilpotency and periodicity
questions as well as injectivity and surjectivity of two-dimensional
CA.

Tarmo Uustalu

Last update 2 September 2010