Reversibility of elementary cellular automata with fully asynchronous updating: An analysis of the rules with partial recurrence

Abstract

Reversibility is a well-studied property for deterministic cellular automata but it is only partially explored when randomness appears in the update or in the transitions. Here, we present a detailed study of 21 finite-size elementary cellular automata with a fully asynchronous updating and periodic boundary conditions. We estimate their degree of reversibility by counting the number of recurrent configurations as a function of the size of the automaton (number of cells). We show that these rules exhibit various qualitative behaviours: some rules show a “strong reversibility” with a number of recurrent configurations that grows exponentially, while other rules have a “weak reversibility” with a linear growth. We also analyse the structure of the communication graph and report various scaling relations for the number of recurrent communication classes. We identify the cases where the divisibility of the size by 2 or 3 introduces some discontinuities in the behaviour. This study completes the characterisation of the 256 elementary cellular automata with regard to their recurrence properties.