ITT8040 -- Cellular Automata

Course code: ITT8040
ECP: 3
Period:13 March--8 May 2013 2013
Time and place: Wednesdays 10:00--12:00 in room B126 of the Institute of Cybernetics (Akadeemia tee 21)
Instructor: Silvio Capobianco (Institute of Cybernetics)
Language: English

Students are required to declare the course in ÕIS.

Aim and scope

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:

Describe global distributed phenomena in terms of local laws.
Understand the role of dimension in decidability problems.
Design distributed systems that can be run in reverse.

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

Lectures

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 Garden-of-Eden theorem	Balancedness theorem. Garden of Eden theorem.	Lecture slides Assignment 3 Correction
3 April 2013	The role of dimension	One-dimensional case. De Bruijn graphs.	Lecture slides Assignment 4 Correction
17 April 2013	Algorithmic questions	Two-dimensional CA and tilings. Algorithms, semi-algorithms 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. Second-order CA. Conserved quantities.	Lecture slides

Prerequisites

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.

Reading material

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.

Download here

Evaluation criteria

The final exam is composed of two parts:

A questionnaire.
Solutions are now available HERE
A presentation based on material related to the subjects touched during the course.

Topic	Reading materials	Speaker
Toffoli's theorem	Tommaso Toffoli. (1977) Cellular automata mechanics. Doctoral thesis, University of Michigan. Chapter 3. Peter Hertling. (1997) Embedding cellular automata into reversible ones. Research report, University of Auckland.	Maksim Gorev
Kari's theorem for 2D reversible CA	Jarkko Kari. (1996) Representation of Reversible Cellular Automata with Block Permutations. Mathematical Systems Theory 29, 47--61.	Niccolò Veltri
Conservation laws in rectangular CA	Tim Boykett, Jarkko Kari, and Siamak Taati. (2006) Conservation Laws in Rectangular CA. Journal of Cellular Automata 3(2), 115--122.	Radu Prekup
The firing squad synchronization problem	F.R. Moore and G.G. Langdon. (1968) A Generalized Firing Squad Problem. Information and Control 12, 212--220.	Elmo Todurov