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.