On linear cellular automata (with special focus on rule 90)

Silvio Capobianco

Institute of Cybernetics

Thursday, 25 September 2014, 14:00
Cybernetica Bldg (Akadeemia tee 21), room B101

Slides from the talk [pdf]

Abstract: Cellular automata (CA) are models of synchronous parallel computation, where the next state of a cell depends on the current state of finitely many neighbors.

If the set of states is a commutative ring with unity, it may be that the local update function is linear in its arguments. In this case, the global transition function on configurations obeys a superposition principle. In addition, algebraic tools such as Laurent series can be applied to the study of global dynamics.

In the first half of this talk, we will discuss the basics of the theory of linear cellular automata in arbitrary dimension, and observe some noteworthy phenomena. In the second half, we will discuss rule 90 (which is the one-dimensional rule where the next state of each cell is the exclusive OR of the current states of its nearest neighbors) in the case of finite toroidal support, display the structure of the orbits, and provide some upper bounds on their lengths.

Tarmo Uustalu
Last update 25 September 2014