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

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