Tilings and undecidability in cellular automata

Jarkko Kari

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.

ERDF
Tarmo Uustalu
Last update 2 September 2010