Causal Graph Dynamics extend Cellular Automata to arbitrary, bounded-degree, time-varying graphs. The whole graph evolves in discrete time steps, and this global evolution is required to have a number of physics-like symmetries: shift-invariance (it acts everywhere the same) and causality (information has a bounded speed of propagation). We study a further physics-like symmetry, namely reversibility. We extend a fundamental result on reversible cellular automata by proving that the inverse of a causal graph dynamics is a causal graph dynamics. We also address the question of the evolution of the structure of the graphs under reversible causal graph dynamics, showing that any reversible causal graph dynamics preserves the size of all but a finite number of graphs.
展开▼
