Students are required to declare the course in ÕIS.
Participants will become acquainted with the classical theory of cellular automata, its main results, and its basic methods.
Upon successful completion of the course, students should be able to:
Cellular automata (briefly, CA) are dynamical systems on regular (possibly infinite) grids, characterized by having a finitary description in terms of a finite alphabet, a finite neighborhood, and a finitary local function which, applied synchronously at each node of the grid, determines the next global state given the current one. Applications are manifold, from physics to social sciences. Their theory is also rich of noteworthy phenomena.
After giving the basic definitions, we will explore the first remarkable properties: existence of the reverse CA when the global function is bijective; balancedness of surjective CA; and the celebrated GardenofEden theorem by Moore and Myhill. Onedimensional CA constitute a very special case, with graphbased algorithms to decide injectivity and surjectivity of the global map: we will discover that such problems are undecidable in higher dimension. We will then examine some techniques that ensure that the resulting CA is reversible.
A detailed program of the course can be found HERE
Date  Title  Topics  Files 
13 March 2013  Introduction  Introduction. Conway's Game of Life. Basic definitions. Elementary CA. Finite and periodic configurations. Compactness principle. 
Assignment 1
Correction 
20 March 2013  First theorems  Basic facts. Reversible CA. Balance. (definition) 
Assignment 2
Correction Note on periodic configurations 
27 March 2013  The GardenofEden theorem  Balancedness theorem. Garden of Eden theorem. 
Lecture slides
Assignment 3 Correction 
3 April 2013  The role of dimension  Onedimensional case. De Bruijn graphs. 
Lecture slides
Assignment 4 Correction 
17 April 2013  Algorithmic questions  Twodimensional CA and tilings. Algorithms, semialgorithms and undecidability. 
Lecture slides
Assignment 5 Correction 
19 April 2013  Undecidability  Turing machines. Undecidability in tiles. Undecidability of nilpotency and 2D  Lecture slides 
24 April 2013  Undecidability and universality  Undecidability in cellular automata (cont.) Computational universality. 
Lecture slides
Assignment 6 Correction 
29 April 2013  Reversible CA  Partitioned CA.  Lecture slides 
8 May 2013  Conserved quantities.  Block CA. Margolus neighborhood. Secondorder CA. Conserved quantities.  Lecture slides 
Participants are supposed to be familiar with the basics of automata theory and graph theory, such as can be provided by YMA5720  Discrete Mathematics or ITT0030  Discrete Mathematics II.
This course is based on the lecture notes by Prof. Jarkko Kari (University of
Turku) for his own Spring 2011 course "Cellular Automata".
We thank Prof. Kari for his kind permission.
The final exam is composed of two parts:
Topic  Reading materials  Speaker 
Toffoli's theorem 

Maksim Gorev 
Kari's theorem for 2D reversible CA 

Niccolò Veltri 
Conservation laws in rectangular CA 

Radu Prekup 
The firing squad synchronization problem 

Elmo Todurov 