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.