ITT8040 -- Cellular Automata

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:

Contents

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.

Evaluation criteria

The final exam is composed of two parts:

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

Last update: June 12, 2013

Valid HTML 4.01 Transitional