Norman Margolus

Center for Computational Science, Boston University and

Laboratory for Computational Science, Massachusetts Institute of Technology

Raissa D’Souza

Department of Physics and Artificial Intelligence Laboratory,

Massachusetts Institute of Technology

A Cellular Automaton (CA) can be thought of as a uniform crystalline arrangement of simple identical processors called “cells.” These processors are locally interconnected, and operate synchronously. CA computations are well matched to the potentialities and constraints of large-scale crystalline arrangements of atoms. CA hardware built out of macroscopic arrays of near-atomic-scale elements may one day provide us with parallel computation with a speed, density and size that cannot be approached in a non-CA format. Today’s rudimentary CA machines let us begin to develop and study large-scale crystalline algorithms. Although none of the simulations shown here involve more than a few million CA cells, simulations many orders of magnitude larger are both economically and technologically feasible today.

In this video, we demonstrate a few CA models that fall into the category of “discrete particle simulations of physics.” For example, we show a simple seminumerical lattice gas simulation illustrating alternating vortex shedding in hydrodynamic flow past an obstacle. This kind of model combines many of the best aspects of finite difference schemes and molecular dynamics. We also show an example of a simple reversible CA which exhibits large-scale pattern formation. This system has a realistic entropy, and serves as a laboratory for studying the thermodynamics of pattern formation. It is also illustrative of a wide range of realistic dynamical and statistical mechanical models that can be brought to life as computational CA models. In general, CA models of physics are currently most interesting computationally in situations that fall between the reach of macroscopic equations and of molecular dynamics.

Segment 1A: Cellular Automata diffusion.

Segment 1B: Cellular Automata diffusion with reversed particle dynamics.

Segment 2: A seminumerical lattice gas model.

Segment 3A: A simple reversible CA rule, implemented in a 3D space. A cross-section of the system is rendered using discrete CA light.

Segment 3B: To show the structure of the final pyramidal pattern, the plane of rendering is brought forward to the edge of the 3D space, then back to the center.

**Hardware:** 8-processor CAM-8 CA machine, developed by the first author in collaboration with the MIT/LCS Information Mechanics Group

**Software:** “Step-6.0”, a custom CAM-8 simulation and visualization environment written by the first author.

**Graphics programming and video production:** Robert Putnam and Laura Giannitrapani, Scientific Computing and Visualization Group, Boston University.

**Acknowledgments:** The CAM-8 work was supported by DARPA, under grant N0014-89-J-1988 and contract DABT63-95-C-0130. The integer lattice gas model was developed jointly by J. Yepez of the U.S. Air Force; and B. Boghosian, F. J. Alexander, and N. Margolus of the BU Center for Computational Science. This lattice gas research was supported by AFOSR (initiative 2304CP and grant F49620-95-1-0285) and by Phillips Laboratory.