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 Garden-of-Eden theorem by Moore and Myhill. One-dimensional CA constitute a very special case, with graph-based 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
|13 March 2013||Introduction||Introduction. Conway's Game of Life. Basic definitions. Elementary CA. Finite and periodic configurations. Compactness principle.||
|20 March 2013||First theorems||Basic facts. Reversible CA. Balance. (definition)||
Note on periodic configurations
|27 March 2013||The Garden-of-Eden theorem||Balancedness theorem. Garden of Eden theorem.||
|3 April 2013||The role of dimension||One-dimensional case. De Bruijn graphs.||
|17 April 2013||Algorithmic questions||Two-dimensional CA and tilings. Algorithms, semi-algorithms and undecidability.||
|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.||
|29 April 2013||Reversible CA||Partitioned CA.||Lecture slides|
|8 May 2013||Conserved quantities.||Block CA. Margolus neighborhood. Second-order 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:
|Kari's theorem for 2D reversible CA||
|Conservation laws in rectangular CA||
|The firing squad synchronization problem||