Macroscopic order from reversible lattice growth models

Raissa M. D'Souza and Norman H. Margolus

The Problem:

We seek to understand mechanisms for the emergence of large scale macroscopic order from local invertible microscopic dynamics.


Pattern formation is an intrinsically dissipative process, however the laws of physics are microscopically reversible: there is no dissipation at the microscopic scale. We are interested in simple systems which organize into patterns through microscopically reversible dynamics. They model how dissipation arises (i.e., how information flows between the macroscopic and the microscopic degrees of freedom), and provide a clear example of how to reconcile the macroscopic irreversibility that gives rise to patterns with the microscopic reversibility adhered to by physical processes. Aside from providing a laboratory in which to probe the thermodynamics of pattern formation, implementations of reversible microscopic models, and the understanding of invertible dynamics in general, have technological significance, as discussed below.

Previous Work:

A review of the limited amount of previous work on reversible microscopic models can be found in Ref.[1]. Several of the models discussed therein use techniques introduced to study reversible dynamics of spin systems on a lattice[2]. Previous work explicitly in the field of pattern formation has focused on irreversible microscopic mechanisms, with examples ranging from crystal growth, to Turing patterns in chemical reactions, to patterns formed by growing bacterial colonies[3].


We build models which attempt to capture aspects of classical physics: the models are local, deterministic, have exact conservations, and are exactly microscopically reversible. We implement the models as lattice gas cellular automata, on a special purpose cellular automata machine, the CAM8[4] (which was developed here at MIT in the course of the past decade). The analysis of the models relies primarily on the standard techniques of statistical mechanics, which enables the prediction of macroscopic quantities through a statistical analysis of the microscopic details of the system. In some cases we can also directly take the continuum limit of the discrete, microscopic dynamics to establish the partial differential equations obeyed in the macroscopic limit for the system.

(a) (b)

(a) A typical equilibrium cluster generated by the RA model. This cluster has undergone a transition from a dense bushy morphology to the branched polymer shown above. (b) The asymptotic state of the three-dimensional SAME rule. We render a cross section through the center of the space. This is a stable, dynamical structure: there are small microscopic fluctuations at each time step, yet the macroscopic structure will persist for longer than we could possibly observe it.

Two interesting systems we are concurrently studying are the Reversible Aggregation (RA) model and the three-dimensional SAME model. The first model is of cluster growth via the diffusive aggregation of particles in a closed system. The particles release latent heat into a heat bath upon aggregating, while singly connected cluster members can absorb heat and evaporate. Initially the heat bath is empty, so aggregation events happen more readily than evaporation. The heat bath quickly reaches a steady state, meaning the system now has a well defined temperature, and that the net number of aggregation and evaporation events are equal. The growth morphology of the cluster correspondingly undergoes a transition from the typical ``frost on a window pane'' pattern observed for irreversible models of diffusive cluster growth[5], to the highest entropy macrostate allowed for a connected cluster in a finite volume, a branched polymer. We have studied the thermodynamics of this model extensively, as well as quantifying the transition in the resulting growth morphology via the fractal dimension of the clusters[6].

The second model, the three-dimensional SAME model, provides a nice example of the emergence of large scale order with no explicit entropy sink (i.e., no heat bath). The model is a generalization of the dynamical Ising model[2] of binary spins on a lattice which interact with nearest neighbor sites. The system evolves so as to maximize the entropy. In the analogous two dimensional dynamics we observe this system evolve from a small block of randomness in a uniform background to a completely random and disordered state. In contrast, in three dimensions the system evolves from a small cube of randomness to a stable dynamical structure with long range order resembling a square pyramid embedded in fluctuating spherical shells. Discrete systems have a finite, but extremely large, number of distinct microscopic states. In general, reversible systems visit almost all of the states before cycling back to the initial state, thus the stable structure generated by the SAME model will persist for longer than we could ever possibly observe it. A general discussion of this model and of cycle times in discrete reversible systems appears in Ref.[1], a detailed discussion will appear in the soon to be released thesis of the first author.


The primary difficulty we encounter is trying to incorporate more physics into our models---the constraints of locality, exact conservation, and invertibility can be hard to reconcile with an interesting macroscopic dynamics. We would also like to analyze the macroscopic dynamics of physics-like discrete systems using the language of physics. This would require the formulation of the least action principle and the Euler-Lagrange equations for discrete systems. By studying simple models we hope to gain insights useful for dealing with this more general issue.


Understanding the mechanisms of pattern formation has obvious significance. By modeling the entire process of pattern formation, including the dissipation, we hope to emulate the mechanisms of nature much more accurately than do irreversible models. The development of invertible dynamics and algorithms has further technological significance such as pushing down the barrier to atomic scale computing. Each bit of information erased during a computation releases heat into the environment. Heat is created in proportion to the volume of the computer, yet heat leaves the computer only in proportion to the surface area. Hence, as logic gate density in computers increases, the use of an invertible dynamics (which does not erase information and hence does not need to produce heat) will be required to keep the mechanical parts from burning up. If we are to succeed in building quantum computers they too will require invertible microscopic algorithms, as the laws of quantum mechanics are unitary (and hence microscopically reversible).

Research Support:

Support for this research was provided by the DARPA Reversible Computing Project, contract number DABT63-95-C-0130.


[1] N. H. Margolus, "Crystalline Computation", in Feynman and Computation, Addison-Wesley, 1998.
[2] M. Creutz, "Deterministic Ising Dynamics", Annals of Physics 167, 1986.
[3]A. L. Barabasi and U. E. Stanley, Fractal Concepts in Surface Growth, Univ. of Cambridge Press, New York, 1995; J. E. Pearson, "Complex Patterns in a Simple System", Science 261, 1993.; E. Ben-Jacob et al.,"Response of bacterial colonies to imposed anisotropy", Physical Review E 53, 1996.
[4] N. H. Margolus, "CAM-8: a computer architecture based on cellular automata", in Pattern Formation and Lattice-Gas Automata, American Mathematical Society, 1996.
[5] T. A. Witten and L. M. Sander,"Diffusion-Limited Aggregation: a kinetic critical phenomenon",Physical Review Letters 47, 1981.
[6] R. M. D'Souza and N. H. Margolus,"Reversible aggregation in a lattice gas model using coupled diffusion fields",submitted to Physical Review E, 1998.