\catcode`\@=11

\def\refnum#1{\if@filesw\immediate\write\@auxout{\string\citation{#1}}\fi
  \def\@citeb{#1}
  {\hbox{Reference~\csname b@\@citeb\endcsname}}}

\def\@cite#1#2{\raise.8ex\hbox{\scriptsize \ {#1\if@tempswa , #2\fi}}}

\catcode`\@=12

\documentstyle[expsfig]{article}

\font\tenbf=cmbx10
\font\tenrm=cmr10
\font\tenit=cmti10
\font\elevenbf=cmbx10 scaled\magstep 1
\font\elevenrm=cmr10 scaled\magstep 1
\font\elevenit=cmti10 scaled\magstep 1
\font\ninebf=cmbx9
\font\ninerm=cmr9
\font\nineit=cmti9
\font\eightbf=cmbx8
\font\eightrm=cmr8
\font\eightit=cmti8
\font\sevenrm=cmr7

\textwidth 5.0in
\textheight 8.0in
\pagestyle{empty}
\topmargin -0.25truein
\oddsidemargin 0.30truein
\evensidemargin
 0.30truein
\raggedbottom
% new macro for bibliography
\newcommand{\bibit}{\nineit}
\newcommand{\bibbf}{\ninebf}
\newcommand{\mysection}[1]{\vglue 0.6cm
\stepcounter{section}
{\tenbf\noindent \thesection. #1 \hfil}
\vglue 0.4cm}
\newcommand{\mysubsection}[1]{\vglue 0.6cm
\stepcounter{subsection}
{\tenit\noindent \thesubsection. #1 \hfil}
\vglue 0.4cm}

\renewenvironment{thebibliography}[1]
 { \ninerm
   \begin{list}{\arabic{enumi}.}
    {\usecounter{enumi} \setlength{\parsep}{0pt}
     \setlength{\itemsep}{3pt} \settowidth{\labelwidth}{#1.}
     \sloppy
    }}{\end{list}}
\renewcommand{\thefootnote}{\fnsymbol{footnote}}
\parindent=3pc
\baselineskip=12pt

%\date{January 21, 1994}

%%%% Single-column figure, given here
 \newcommand{\figgiven}[3]{% label, picture, caption
 \begin{figure}[tbp]
  $$#2$$\relax
  \caption{{\ninerm #3}}
 \label{fig.#1}
 \end{figure}                 }

%%%% Two-column figure, given here
 \newcommand{\figtwogiven}[3]{% label, picture, caption
 \begin{figure*}[tbp]
  $$#2$$\relax
  \caption{{\ninerm #3}}
 \label{fig.#1}
 \end{figure*}                 }


\begin{document}

\def\asic{{\sc asic}}
\def\vlsi{{\sc vlsi}}
\def\cam{{\sc cam}}
\def\Cam{{\sc Cam}}
\def\sram{{\sc sram}}
\def\ram{{\sc ram}}
\def\dram{{\sc dram}}
\def\fpga{{\sc fpga}}
\def\arpa{{\sc arpa}}
\def\sparc{{\sc sparc}}

\begin{center}
\vglue 0.6cm
{{\elevenbf CELLULAR AUTOMATA MACHINES:\\}
 {\tenbf        \vglue 10pt
               A NEW KIND OF COMPUTER\footnote{
\sevenrm\baselineskip=10pt This research was supported by the Advanced
Research Projects Agency, grant N0014-89-J-1988.}
\\}
\vglue 1.0cm
{\tenrm NORMAN MARGOLUS \\}
\baselineskip=12pt
{\tenit MIT Laboratory For Computer Science\\}
\baselineskip=11pt
{\tenit Cambridge Massachusetts 02139, U.S.A\\}}

\vglue 0.8cm
{\tenrm ABSTRACT}
\end{center}

%Typeset the abstract with an indentation
%of 3 picas on the left and right margins and in 10 point roman with
%baselineskip of 11 point.

\vglue 0.3cm

{\rightskip=3pc
 \leftskip=3pc
 \tenrm\baselineskip=11pt

\noindent As computer hardware makes use of increasingly
microscopic physical effects, the attractiveness of uniform arrays of
simple logic, locally interconnected, becomes correspondingly greater.
These kinds of Cellular Automata (CA) based computers can, in
principle, achieve a computational density that is near the maximum
allowed by the laws of physics.  CA based computers are also
indefinitely extendable without slowing down the machine clock---such
machines may one day have macroscopic numbers of microscopic computing
elements.

}

{\rightskip=3pc
 \leftskip=3pc
 \tenrm\baselineskip=11pt

\medskip\noindent Conventional computers are so poor at CA
calculations that they completely obscure the enormous inherent
efficiency of this uniform parallel paradigm, and so discourage work
on CA models.  By making inexpensive machines that are a few orders of
magnitude more efficient for large-scale CA calculations, we hope to
encourage researchers in a variety of fields to begin to develop and
investigate CA models.

}

\mysection{Computers without wires}

For the past 20 years, feature sizes of computing elements have
decreased at a rather constant exponential rate.  If these trends are
extrapolated forwards, we will have computing elements the size of an
atom in about 20 years.

Clearly there are new kinds of difficulties, and new kinds of physics,
that will intervene as we try to scale down towards atomic dimensions.
One of the first difficulties we will encounter will be with wires.
Trying to make conducting elements that are very narrow, and trying to
drive them with near-atomic-scale systems will be a tremendous
problem.

One solution is to build computers that have no wires.  Uniform arrays
of computing elements, each interacting directly with adjacent
elements, can perform any computation.  Such arrays can, in principle,
operate without any wires\cite{teich,lloyd,biafore}.  Since the speed
of light is a constraint on information propagation, short signal
paths translate into fast operation.  With very little time or space
wasted on signal propagation, clock speeds and logic densities can be
very high.  In fact, these kinds of Cellular Automata (CA) based
computers can, in principle, achieve a computational density that is
near the maximum allowed by the laws of physics.  CA based computers
are also indefinitely extendable without slowing down the machine
clock---such machines may one day have macroscopic numbers of
microscopic computing elements.

Programming such a machine is much like programming a digital version
of the laws of physics.  The dynamics is perfectly uniform---all of
the complexity is in the initial state.  In physics, when you build a
computer, what you actually do is set up an initial state for the
uniform laws of physics that acts like a computer: atoms of conductor
here, atoms of semiconductor there, and so on.  To make a CA compute,
you do the same thing: some cells might be given an initial state that
causes them to pass signals straight through (thus acting like wires),
others might combine signals and perform logical operations on them,
etc.  There are very simple CA rules known which are universal, in the
sense of supporting arbitrarily complex computer
circuitry\cite{margolus-bbm}.

%maps into space well

Long before we approach the atomic realm, there are good reasons for
interest in computing hardware with only local interconnectivity.
Even at the level of current \vlsi{} technology, arrays of simple
processors with short (local) signal paths could achieve enormous
computational density, speed, and size.

Conventional computers are so poor at CA calculations that they
completely obscure the enormous inherent efficiency of this uniform
parallel paradigm, and so discourage work on CA models (and hence also
on CA machines).  By making inexpensive machines that are a few orders
of magnitude more efficient for large-scale CA calculations, we hope
to encourage researchers in a variety of fields to begin to develop
and investigate CA models.


\mysection{Machines for investigating the large-scale behavior of CA}

\figtwogiven{system}{ \hfill\psfig{figure=system.ps,height=2in} \hfill
}{\Cam-8 system diagram. (a)~A single processing node, with \dram{}
site data flowing through an \sram{} lookup table and back into \dram.
(b)~Spatial array of \cam-8 nodes, with nearest-neighbor (mesh)
interconnect (1 wire/bit-slice in each direction).}

The Information Mechanics Group at the MIT Laboratory for Computer
Science has been involved for over a decade in the design and use of
Cellular Automata Machines
(\cam's)\cite{cam5,margolus-bbm,cambook,super,cam8-book}.  This work
was stimulated by our frustration with the inadequacy of conventional
computers for CA simulation.  We were investigating some simple
reversible CA dynamics\cite{margolus-bbm}, which took about a minute
per frame on our best workstations of the day.  My collaborator Tom
Toffoli built our first CA hardware---basically a glorified
framebuffer\cite{cam5}.  I've been the architect of our latest CA
machine (\cam-8), which is optimized for large-scale physical
simulation using lattice-gas-like
rules\cite{cam8-book,patent,step1,nhm-waterloo}.

The fastest CA hardware would be a fully parallel array of logic.
Speed, however, has not been our only concern.  In the first machine,
Tom wanted to be able to see CA run with the speed and resolution of a
TV picture---to bring CA to life.  This could be achieved with a
single lookup-table processor being time-shared over an array of cells
kept in conventional memory chips.  This was a very economical
architecture, and we eventually ``published'' a version of this
machine along with a book about it\cite{cambook} and an extensive
collection of CA modeling examples\cite{cam6-soft}.

Our latest machine continues to use lookup tables for flexibility and
speed, and conventional memory chips for holding the cell state
information.  Except for a chip of our design for knitting together
lookup-table (\sram) processors with (\dram) cell-state information,
this machine consists entirely of commodity memory chips running at
full memory bandwidth.  This allows us to simulate large spaces
economically, and with a flexible choice of updating rules, while
still retaining enough speed so that small assemblages of such
hardware are the fastest CA machines in the world.

Figure~\ref{fig.system}a depicts a single hardware module of \cam-8.
Spatially organized site data is scanned out of the cell-array, passed
through a lookup table, and returned to the cell-array.  In this
machine, the cell-array can be configured to be $n$-dimensional, and
the data-movement is mostly by relative pointer addressing.
Figure~\ref{fig.system}b illustrates an array of such modules---drawn
as two-dimensional, the array would normally be three-dimensional.
All modules operate in lockstep, with nearest-neighbor interconnection
between modules.  The data movement involves 16 independent
bit-slices, and there is one wire per bit-slice per direction for
communication.

\mysubsection{Lattice-gas-like data movement}

\figtwogiven{hpp}{ \hfill%
\vbox{%
\psfig{figure=layers.ps,height=2in}%
}%
\hskip.3in%
\vbox{%
\psfig{figure=sound2.ps,height=2in}%
}\hfill
}{The HPP lattice gas (a)~Data movement of the four
particle components.  (b)~Sound pulse simulation.}

Data movement is lattice-gas-like.  To illustrate this, consider the
simple HPP lattice gas\cite{hpp} depicted in Figure~\ref{fig.hpp}.
This is a fully discrete molecular dynamics, with only four particle
directions, and a single particle speed.  When particles collide
head-on, they come out at right-angles to their original motion;
otherwise particles always go straight.  Thus we have a
microscopically reversible, momentum conserving dynamics.

To implement this as a CA model, think of a two-dimensional space with
four-bit {\em cells} (if this was a frame-buffer, we would call these
{\em pixels}).  We group corresponding bits from every cell into {\em
bit-planes}.  Figure~\ref{fig.hpp}a shows the motion of the four
bit-planes used to implement the HPP models.  Wherever we want a
particle going north, we put a 1 on bit-plane 0.  A partice going
south is a 1 on plane 1, etc.  Data movement is implemented by moving
each bit plane by one position in the indicated direction.  Then we
perform collisions by looking at each cell, and tranforming each cell
that contains only a north-going and a south-going particle into one
that contains an east-going and a west-going one, and vice versa.
Otherwise the cells are left unchanged.

On a single module of \cam-8, each bit-plane is kept in a separate
\dram{} chip, and data movement is achieved by programming appropriate
address offsets.  The work of updating each cell with the HPP
collision rule is done by table lookup: the hardware scans through
every cell in the space, passing the data through a lookup table and
putting the updated value back into the cell array.

Figure~\ref{fig.hpp}b shows a ``snapshot'' from a \cam-8 HPP
simulation illustrating the propagation of a sound pulse.  The space
is 1K$\times$1K and was started from a random distribution of
particles, but with a 128$\times$128 particle vacuum in the center.
The simulation runs at about 800 million site updates per second on
our workstation-scale prototype \cam-8 machine.

Of course the actual hardware is more general than is needed for the
HPP lattice gas.  There are physically 16 bit-planes---really bit
hyper-planes since they can be $n$-dimensional---and any number of
planes can be simulated.  The lookup tables are 16-bits wide, so any
update is accomplished as a composition of 16-bit operations.  Lookup
tables are double buffered, so that while the space is being scanned
with one table, the next table can be broadcast to the machine---the
number of different tables that may be composed to achieve an updating
is limited only by the memory of the workstation controlling the CA
machine.  Most importantly, \cam-8 is an indefinitely extendable 3D
array of processors all operating in lockstep.  All communication and
updating is completely synchronized and pipelined, so that every
processing module has all of the data it needs to complete a
cell-update at every machine clock.

Notice that the physical interconnection between processors is
nearest-neighbor at the level of modules, rather than at the level of
the fine-grained cells that are being simulated.  This means that the
natural neighborhood volume accessible for use during updating each
cell involves {\em millions} of nearby cells.  Despite the
nearest-neighbor module constraint, shifts can be in arbitrary
directions---this is accomplished in the hardware by communicating in
different directions at different points in the updating pipeline.

Finally, note that by an appropriate sequence of uniform data
movements and local data interactions, any spatially organized
calculation can be accomplished.  Thus \cam-8 is a completely general
purpose machine for uniform, spatially organized calculations.
Calculations that involve the interaction of relatively few bits at a
time at each spatial site can be implemented most efficiently.


\mysubsection{A high level machine language}\label{high-level}

\begin{figure*}[tbp]
  \centering
 {$
\vcenter{\hsize=4in\small\begin{verbatim}
new-experiment        512 by 512 space

                      0 0 == north  1 1 == south
                      2 2 == east   3 3 == west

define-rule hpp-rule  north south =  east west =  and
                      if east <-> north  west <-> south then
end-rule

define-step hpp-step  lut-data   hpp-rule
                      site-src   lut
                      lut-src    site
                      kick       north field -1 y
                                 south field  1 y
                                 east  field  1 x
                                 west  field -1 x
                      run        new-table
end-step\end{verbatim}}
 $}
\caption{{\ninerm Complete machine-language code for an HPP simulation.}}
\label{fig.hpp-code}
\end{figure*}

Figure~\ref{fig.hpp-code} lists the complete code for the HPP
simulation shown in Figure~\ref{fig.hpp}.  The code consists of some
definitions of {\em data-fields}, the definition of an updating rule,
and the definition of an updating step (rule, data paths, and data
movement).  This is an assembly-language level program for \cam-8.  It
results in about a dozen machine-language instructions being broadcast
to the \cam-8 hardware.  This program serves to illustrate how
directly simple lattice gas models map into the architecture.

Despite being at such a low level, this program runs without change on
a machine with any number of modules.\footnote {Utilities that
download initial patterns and that manage the video display are not
shown here.  Unlike the definition of the dynamics given in the
figure, the actions of initialization, visualization, and analysis
utilities does generally depend explicitly on the size and shape of
the space.} Issues such as making the data move smoothly across module
boundaries are handled directly by the hardware.

For an overview of the \cam-8 architecture and its applications, see
\cite{nhm-waterloo}.  For a detailed description of our prototype
\cam-8 implementation, including the \cam-8 register model, the
workstation interface, and system configuration and initialization,
see ``STEP: a Space Time Event Processor\cite{step1}.''


\mysection{Physics applications}

\figtwogiven{particles}{ \hfill%
\vbox{%
\psfig{figure=dla.ps,height=2in}%
}%
\hskip.3in%
\vbox{%
\psfig{figure=ising.ps,height=2in}%
}\hfill
}{\Cam-8 used for simulating physics. (a)~Diffusion limited
aggregation.  (b)~Deterministic Ising dynamics, in contact with heat bath.}

CA models are already the best computational methods known for certain
physical systems, {\em even on conventional
computers}\cite{kadanoff89,rothman90a,rothman92}.  Thus it makes sense
to concentrate on these kinds of models first.  For this reason,
\cam-8 is optimized for CA simulations of
physics\cite{super,cambook,waterloo}.

Figures~\ref{fig.particles}, \ref{fig.matter}, and \ref{fig.fhp7} show
some simple examples of CA models of physics run on a small prototype
\cam-8.  This 8-node machine contains less memory and logic than its
SPARCstation front-end, and runs at the same clock rate.  For these
kinds of simulations, this small machine is about as fast as any
computer in the world.  Implementations that will be hundreds of times
larger are underway.

Figure~\ref{fig.particles}a shows a two-dimensional diffusion-limited
aggregation model\cite{cambook}.  The space is $1024\times1024$ and
the diffusion is driven by high-quality random variables generated
directly by \cam-8.  The system shown in the Figure was started with a
single fixed ``seed'' particle and about 100,000 diffusing particles.
Whenever a diffuser touches a fixed particle, it becomes fixed at that
position.  The simulation runs at about 800 million site-updates per
second on the prototype, and the Figure shows the state after about 2
minutes of evolution.

Figure~\ref{fig.particles}b shows another statistical-mechanics
simulation\footnote{Tommaso Toffoli wrote this simulation, and
prepared this Figure.}.  This is a simple deterministic Ising dynamics
in contact with a spatially distributed heat bath\cite{creutz}.  Spin
variables at each point in space have an energy that depends on
whether or not they are parallel to neighboring spins.  The dynamics
flips spins whenever it is energetically allowed (i.e., if the heat
bath can locally absorb or release the energy required for the
change).  By controlling the energy content of the heat bath, we
control the temperature of the system.  In the figure we have the
system near its critical temperature.  This simulation runs at about
400 million site-updates per second.


\figtwogiven{matter}{ \hfill%
\vbox{%
\psfig{figure=poly3.ps,bbllx=72pt,bblly=520pt,bburx=270pt,bbury=720pt,height=2in}%
}%
\hskip.3in%
\vbox{%
\psfig{figure=therm620.ps,height=2in}%
}\hfill
}{\Cam-8 used for simulating physics. (a)~Polymers
diffusing from an initial concentrated region.  (b)~Spongy
three-dimensional structure obtained by ``majority'' annealing.}

Figure~\ref{fig.matter}a shows a two-dimensional simulation of a CA
polymer model due to Bar-Yam\cite{yaneer-poly,smith92} (the \cam-8
simulation was implemented by M.\ Biafore).  This model employs a
statistical dynamics (controlled by random variables) that uses
space-partitioning\cite{margolus-bbm} in order to allow chains of
monomers to jiggle around without overlapping or breaking.  The
simulation illustrated is on a $512\times512$ space, and runs at about
30 million site updates per second.

Figure~\ref{fig.matter}b illustrates a three-dimensional simulation of
an annealing process, with simultaneous rendering and display.  The
system shown is $512\times512\times64$, and combines random variables
with a local majority rule to implement a rule with surface tension
and clumping.  While the material simulation is going on, we also
simulate ``photons'' of light traversing the system, illuminating the
matter and being reflected.  This simulation produces a complete
rendered image every second update of the space, and runs at 200
million site updates per second, with no additional overhead for the
rendering.

\figtwogiven{fhp7}{ \hfill%
\vbox{%
\psfig{figure=kh.ps,width=2.75in,height=1.65in}%
}%
\hfill }{Momentum flows for Kelvin-Helmholtz shear instability using
the FHP lattice gas.}

Finally, Figure~\ref{fig.fhp7} illustrates the use of \cam-8's
hardware event counters in conjunction with a lattice-gas simulation
to illustrate a Kelvin-Helmholtz shear instability.  This simulation
was done by Jeff Yepez at the U.\ S.\ Air Force's Phillips Laboratory.
The simulation uses a 7-bit FHP model, which runs at a rate of about
400 million site updates per second.  The lattice is 4K$\times$2K
sites, with most of the fluid initially set in motion at Mach 0.4 to
the right, except for a narrow horizontal strip in the middle, which
was given the opposite velocity.  The Figure shows the situation after
40,000 time steps (about 15 minutes of simulation).  Each arrow
represents a block average over a 128$\times$128 region, and over 50
time steps.  These block averages are computed directly by the
hardware, by scanning the space in appropriate blocks and using lookup
tables and event counters to count the net momentum in each block.

\mysection{Conclusions}

Cellular Automata models can be implemented with extreme efficiency
but are underappreciated as computational models, largely because
current computers are so bad at simulating them.  In fact, we have
found that machines can be built with about the same hardware as a
low-end workstation---but configured to take advantage of the
uniformity and regularity of CA calculations---that can perform
large-scale CA calculations about as fast as any computer in the
world.  We've built these machines both in order to satisfy our own
simulation needs, and to encourage other researchers to construct new
CA models.

\mysection{References}

\begin{thebibliography}{99}

	\bibitem{virt-wires} J. {\rm Babb}, R. {\rm
Tessier}, and A. {\rm Agarwal},  in {\it Proceedings of
the IEEE Workshop on FPGAs for Custom Computing Machines}, IEEE
Computer Society Press (1993).
	\bibitem{biafore} M. {\rm Biafore}, {\it Physica \bf 70D}:4
(1994), 415--434.
        \bibitem{creutz} M. Creutz, {\sl Ann.\ Phys.} {\bf 167}
(1986), 62--76.
	\bibitem{doolen} G. {\rm
Doolen}, et al.\ (ed.), {\it Lattice-Gas Methods for Partial
Differential Equations}, Addison-Wesley (1990).
	\bibitem{fhp} U. {\rm Frisch}, B. {\rm Hasslacher}, and Y. {\rm Pomeau},  {\it Phys.\ Rev.\ Lett.} {\bf 56} (1986), 1505--1508.
        \bibitem{hpp} J. {\rm Hardy}, O. {\rm de Pazzis}, and Y. {\rm Pomeau},  {\it Phys.\
Rev.} {\bf A13} (1976), 1949--1960.
	\bibitem{kadanoff89} L. {\rm Kadanoff}, G. {\rm McNamara}, and
G. {\rm Zanetti},  {\it Phys.\ Rev. A} {\bf 40} (1989),
4527--4541.  
	\bibitem{static} H. {\rm Kung},  in {\it
Proceedings of the International Conference on Systolic Arrays}, San
Diego, California, May 1988. 
	\bibitem{waterloo} A. {\rm Lawniczak},
and R.\ Kapral, (eds.)  {\it Pattern Formation and Lattice-Gas
Automata}, American Mathematical Society (1994).
	\bibitem{lloyd} S. {\rm Lloyd}, ``A technologically feasible
quantum computer,'' {\it Los Alamos National Laboratory, Complex
Systems Group Preprint} (1993).
	\bibitem{margolus-bbm} N. {\rm Margolus},  {\it Physica \bf 10\it D} (1984), 81--95.
	\bibitem{cam6-soft} N. Margolus, T. Toffoli, C.  H. Bennett,
G. Vichniac, M. A. Smith, and A. Califano, {\it CAM-6 Software,}
Systems Concepts, San Francisco CA (1984,1987), {\it CAM-PC Software,}
Automatrix Inc., Rexford, NY (1991).
	\bibitem{patent} N. {\rm Margolus}, 
United States Patent and Trademark Office Patent No.~5,159,690,
Filed~09/30/88, Issued~10/27/92. 
	\bibitem{cam8-book} N. {\rm Margolus}, T. {\rm Toffoli},  in
\refnum{doolen}, p.\ 219--249. 
	\bibitem{step1} N. {\rm Margolus}, T. {\rm Toffoli},  {\it
Tech.\ Rep.\ MIT/LCS/TR-592}, MIT Laboratory for Computer Science
(1993).  
	\bibitem{super} N. {\rm Margolus}, T. {\rm
Toffoli}, and G. {\rm Vichniac},  {\it Phys.\ Rev.\ Lett.}
{\bf 56} (1986), 1694--1696. 
	\bibitem{nhm-waterloo} N. {\rm Margolus}, 
in \refnum{waterloo}. 
	\bibitem{teich} K. Obermayer, W. G. Teich, and
G. Mahler, {\it Phys.\ Rev.\ B \sc 37} (1988), 8096--8121.
	\bibitem{yaneer-poly} B. {\rm Ostrovsky}, M. A. {\rm Smith},
M. {\rm Biafore}, Y. {\rm Bar-Yam}, Y. {\rm Rabin}, N.
{\rm Margolus}, and T.  {\rm Toffoli},  in the proceedings of {\it
6th SIAM Conference on Parallel Processing for Scientific Computing},
March 1993. 
	\bibitem{rothman90a} D. Rothman, {\it J.\ Geophys.\ Res.} {\bf
95} (1990), 8663.
	\bibitem{rothman92} D. {\rm Rothman},  in {\it Microscopic Simulations of Complex
Hydrodynamics} (M. {\rm Mareschal} and B. {\rm Holian}, eds.), Plenum
Press (1992). 
	\bibitem{smith92} M.A. {\rm Smith}, Y.\ {\rm Bar-Yam}, Y.
{\rm Rabin}, B. {\rm Ostrovsky}, C. H. {\rm Bennett}, N. {\rm
Margolus}, and T.  {\rm Toffoli},  {\it Computational Polymer Science \bf 2}:4 (1992),
165--171.
	\bibitem{cam5} Tommaso Toffoli, {\it Physica} {\bf 10D}
(1984), 195--204.
	\bibitem{cambook} T. {\rm Toffoli}, and N. {\rm Margolus}, {\it Cellular Automata Machines---a new environment
for modeling}, MIT Press (1987).  
	\bibitem{yepez-cip} J. {\rm
Yepez}, G. {\rm Seeley}, and N. {\rm Margolus},
 submitted
to {\it Computers In Physics}.  \end{thebibliography}

\end{document}


