1. Introduction

>Cellular automata (e.g., Refs. 1 and 2) are arrays of discrete cells with discrete values. Yet sufficiently large cellular automata often show seemingly continuous macroscopic behavior (e.g., Refs. 1 and 3). They can thus potentially serve as models for continuum systems, such as fluids. Their underlying discreteness, however, makes them particularly suitable for digital computer simulation and for certain forms of mathematical analysis.

On a microscopic level, physical fluids also consist of discrete particles. But on a large scale, they, too, seem continuous, and can be described by the partial differential equations of hydrodynamics (e.g., Ref. 4). The form of these equations is in fact quite insensitive to microscopic details. Changes in molecular interaction laws can affect parameters such as viscosity, but do not alter the basic form of the macroscopic equations. As a result, the overall behavior of fluids can be found without accurately reproducing the details of microscopic molecular dynamics.

This paper is the first in a series which considers models of fluids based on cellular automata whose microscopic rules give discrete approximations to molecular dynamics. (1) The paper uses methods from kinetic theory to show that the macroscopic behavior of certain cellular automata corresponds to the standard Navier-Stokes equations for fluid flow. The next paper in the series describes computer experiments on such cellular automata, including simulations of hydrodynamic phenomena.

Figure 1 shows an example of the structure of a cellular automaton fluid model. Cells in an array are connected by links carrying a bounded number of discrete ``particles.'' The particles move in steps and ``scatter'' according to a fixed set of deterministic rules. In most cases, the rules are chosen so that quantities such as particle number and momentum are conserved in each collision. Macroscopic variations of such conserved quantities can then be described by continuum equations.

[ Figure 1 ] Two successive microscopic configurations in the typical cellular automaton fluid model discussed in Section 2. Each arrow represents a discrete ``particle'' on a link of the hexagonal grid. Continuum behavior is obtained from averages over large numbers of particles.

Particle configurations on a microscopic scale are rapidly randomized by collisions, so that a local equilibrium is attained, described by a few statistical average quantities. (The details of this process will be discussed in a later paper.) A master equation can then be constructed to describe the evolution of average particle densities as a result of motion and collisions. Assuming slow variations with position and time, one can then write these particle densities as an expansion in terms of macroscopic quantities such as momentum density. The evolution of these quantities is determined by the original master equation. To the appropriate order in the expansion, certain cellular automaton models yield exactly the usual Navier-Stokes equations for hydrodynamics.

The form of such macroscopic equations is in fact largely determined simply by symmetry properties of the underlying cellular automaton. Thus, for example, the structure of the nonlinear and viscous terms in the Navier-Stokes equations depends on the possible rank three and four tensors allowed by the symmetry of the cellular automaton array. In two dimensions, a square lattice of particle velocities gives anisotropic forms for these terms. A hexagonal lattice, however, has sufficient symmetry to ensure isotropy. In three dimensions, icosahedral symmetry would guarantee isotropy, but no crystallographic lattice with such a high degree of symmetry exists. Various structures involving links beyond nearest neighbors on the lattice can instead be used.

Although the overall form of the macroscopic equations can be established by quite general arguments, the specific coefficients which appear in them depend on details of the underlying model. In most cases, such transport coefficients are found from explicit simulations. But, by using a Boltzmann approximation to the master equation, it is possible to obtain some exact results for such coefficients, potentially valid in the low-density limit.

This paper is organized as follows. Section 2 describes the derivation of kinetic and hydrodynamic equations for a particular sample cellular automaton fluid model. Section 3 generalizes these results and discusses the basic symmetry conditions necessary to obtain standard hydrodynamic behavior. Section 4 then uses the Boltzmann equation approximation to investigate microscopic behavior and obtain results for transport coefficients. Section 5 discusses a few extensions of the model. The Appendix gives an SMP program used to find macroscopic equations for cellular automaton fluids.

previous  l  next