Glider automata on all transitive sofic shifts

Abstract

<p>For any infinite transitive sofic shift <em>X</em> we construct a reversible cellular automaton (that is, an automorphism of the shift <em>X</em>) which breaks any given finite point of the subshift into a finite collection of gliders traveling into opposing directions. This shows in addition that every infinite transitive sofic shift has a reversible cellular automaton which is sensitive with respect to all directions. As another application we prove a finitary version of Ryan’s theorem: the automorphism group <strong>Aut</strong>(<em><strong>X</strong></em>) contains a two-element subset whose centralizer consists only of shift maps. We also show that in the class of <em>S</em>-gap shifts these results do not extend beyond the sofic case.<br><br></p>