Reversible Automata

Reversible cellular automata are not only an interesting subject of study; they have practical applications in coding theory and cryptography. The classical study was published by Gustav A. Hedlund in 1969 [43], in the context of symbolic dynamics rather than automata theory. The paper contains several results, three of which are of central importance for cellular automata:

i)

the transition rules of cellular automata are the continuous, shift-invariant mappings of the full shift,

ii)

in order for every finite configuration to have at least one counterimage, all configurations must have the same number of counterimages, and

iii)

there are indices multiplicative with respect to composition (the Welch indices) which characterize the reversibility of infinite configurations.

Recently Jarkko Kari [46] has published some articles characterizing reversible automata as those arising from block permutations, which is a significant advance in characterizing and classifying the reversible automata.

The first result practically defines celllular automata, although that was not the historical course of events. The others merit further discussion.