[cs-talks] Update- Upcoming Semimars: Theory (Fri)
fgreen1 at bu.edu
Tue Oct 6 12:45:03 EDT 2015
Permutive Cellular Automata
Ilke Torm, BU and University of Turku
Friday, October 9, 2015 at 12pm in MCS 135
Abstract: Cellular automata or CA are certain transformations of infinite grids of states (look up Conway's Game of Life for a famous example). They are defined by a local rule that's applied to every coordinate in a synchronized way. The composition of two CA is again a CA, so we can ask questions about the set of
all cellular automata as an algebraic structure. One interesting question is commutation: given a CA F, which other CA G commute with it, that is, when do we
have F(G(x)) = G(F(x)) on all inputs x?
In this talk I present a result by myself and Ville Salo. We show that so-called permutive CA commute with only very few other CA. Furthermore, permutive CA that also respect the algebraic structure of the state set commute with even fewer CA. In the course of the proof, we prove some interesting facts about the
dynamics of permutive CA. I will first present an easy example, the two-neighbor XOR, and then discuss the more general permutive automata.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the cs-talks