## 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.

### 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.

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:

• 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