Additional comments

The role of topology in treating the evolution of cellular automata is not entirely clear. Hedlund gives it a central role in his fundamental survey [7]; it is basic to such further articles as those of D. Richardson [39] or Tadakazu Sato and Namio Honda [40], and has been used by Karel Culick II [41]. It does seems to be required for the satisfactory description of the limiting behavior of long time evolution [42,43,44].

On the other hand Nasu [8,36,45,46] has been able to obtain extensive results without using topology, at least for one dimensional automata; the present paper likewise demonstrates that no topology is required. We are left with the question of whether there are significantly different results to be obtained from the use of topology or whether topology simply provides a convenient language to express results which could be derived independently. However, this is a topic for a future study, just as is the question of handling two dimensional automata via two dimensional de Bruijn diagrams.

There are also important questions about the applications and the philosophical implications of reversible automata, a preoccupation of Toffoli [20]. Two recent articles addressed to these points are those of Asher Peres [47] and Shinji Takesue [48].

Harold V. McIntosh