20th Estonian Winter School in Computer Science (EWSCS)
XX Eesti Arvutiteaduse Talvekool

Palmse, Estonia, March 1 - 6, 2015

Jarkko Kari

Dept. of Mathematics and Statistics
University of Turku

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.

Course materials


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.

Valid CSS! Valid XHTML 1.0 Strict Last changed April 17, 2016 22:29 Europe/Helsinki (GMT +03:00) by local organizers, ewscs15(at)cs.ioc.ee
EWSCS'15 page: http://cs.ioc.ee/ewscs/2015/