Cellular automata, tilings and (un)computability
Cellular automata are discrete dynamical systems based on local, synchronous and parallel updates of symbols written on an infinite array of cells. They are the simplest imaginable massively parallel computing systems that operate under the nature inspired constraints of locality of interactions and uniformity in time and space. They can also exhibit the physically relevant properties of time reversibility and conservation laws if the local update rule is chosen appropriately. Closely related notions in symbolic dynamics are tiling spaces: sets of infinite arrays of symbols defined by forbidding the appearance anywhere in the array of some local patterns. In comparison to cellular automata, the dynamic local update function has been replaced by a static local matching relation.
These lectures present classical results about cellular automata, discuss algorithmic questions concerning tiling spaces and relate these questions to decision problems about cellular automata, observing some fundamental differences between the one- and two-dimensional cases.
- J. Kari. Cellular automata, tilings and (un)computability. Slides from the EWSCS 2015 course.
- J. Kari. Cellular automata, tilings and (un)computability. Exercises to accompany the EWSCS 2015 course. [pdf]
- Videos from the lectures.
- J. Kari. Cellular automata, tilings and (un)computability. Course notes from the CANT 2012 summer school. 2012.
Jarkko Kari received a PhD in mathematics in 1990 at the University of Turku, Finland. Since then he has worked for the Academy of Finland, Iterated Systems Inc., the University of Iowa, and the University of Turku, where he currently holds a position as a professor of mathematics. Jarkko Kari has supervised six PhD theses, and published over 90 research articles on automata theory, cellular automata and image processing.
April 17, 2016 22:29 Europe/Helsinki (GMT +03:00)
local organizers, ewscs15(at)cs.ioc.ee
EWSCS'15 page: //cs.ioc.ee/ewscs/2015/