University of Turku, Dept. of Mathematics
Wednesday, 1 September 2010, 14:00
Cybernetica Bldg (Akadeemia tee 21), room B 101
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.
— Silvio Capobianco 2010/08/30