Problem 6

How does thermodynamics apply to cellular automata?

Thermodynamics is supposed to describe the average overall behaviour of physical systems with many components. The microscopic dynamics of these systems is assumed to be reversible, so that the mapping from one state to another with time is invertible. Most cellular automata are irreversible, so that a particular configuration may arise from several distinct predecessors. However, a small subset of cellular automaton rules are bijective or invertible. Complete tables of invertible rules exist for , [19, 20] and for , [20], but in general no efficient procedure for finding such rules is known. Nevertheless, it is possible to construct particular classes of invertible rules [16, 21].

To apply thermodynamics one must also ``coarse-grain'' the system, grouping together many microscopically-different states to mimic the effect of imprecise measurements. Coarse-graining in cellular automata may be achieved by applying an irreversible transformation, perhaps a cellular automaton rule, to the cellular automaton configurations. A simple example would be to map the value of every other site to zero.

Coarse-grained entropy in reversible cellular automata should follow the second law of thermodynamics, and be on average non-decreasing with time. One may start from a set or ensemble of configurations with non-maximal coarse-grained entropy. The degrees of freedom that do not affect the coarse-grained entropy are undetermined, and are assumed to have maximal (fine-grained) entropy. In reversible class 2 cellular automata, the determined and undetermined degrees of freedom do not mix significantly with time, and the coarse-grained entropy remains essentially constant. But for class 3 and 4 cellular automata, the degrees of freedom mix, and the coarse-grained entropy increases towards its maximum possible value.

As in all applications of thermodynamics, the question arises of what coarse-graining prescriptions and ensembles of initial states are permissible. The initial states could for example be specially chosen so as to be the predecessors of a low coarse-grained entropy ensemble. The coarse-grained entropy would then decrease. Such examples do not seem physically reasonable. But it has never been clear exactly what mathematical criteria should be imposed to exclude them. One possibility is that one could require the coarse-graining procedure and the initial ensemble to be computationally simple (cf. [22]). If the cellular automaton evolution were computationally irreducible, then such a criterion could exclude ensembles obtained by reversing the evolution for many steps.

For the usual case of irreversible cellular automata, coarse-graining is usually of little consequence: the progressive contraction in the number of states generated by the cellular automaton evolution soon far outweighs the reduction associated with coarse-graining.

previous  l  next