For an example of a CA that allows a particle moving through a universe to modify the universe it moves through, see http://arxiv.org/abs/1002.4841 , "Lattice gas simulations of dynamical geometry in two dimensions" by Anna Klales, Donato Cianci, Zachary Needell, David A. Meyer, and Peter J. Love. Jim Propp