Norm Margolus
I am a Research Affiliate at the MIT Computer Science and Artificial
Intelligence Laboratory.
My first love is the physics of information and computation, and
the informational modeling of physics. This was the subject of
my PhD thesis (MIT
Physics 1987), and has been the focus of most of my subsequent
research. I was privileged to work with Edward Fredkin, Tom Toffoli
and Charles Bennett at
the MIT Information
Mechanics Group between 1980 and 1995, first as a PhD student, and
then as a Research Scientist.
At MIT, in addition to (and often instead of) more theoretical
work on physics
and on reversible
cellular automata, I worked with Tom Toffoli on the design and use
of cellular automata machines, and
led the CAM8 CA
machine project, working closely with Tom. CAM8 was a
spatiallyorganized mesharchitecture multiprocessor that provided a
tool for investigating the possibilities of the kind of largescale
finegrained parallelism that is available in nature. It was
successful in this, but the project ended at the prototype stage,
before CAM8 machines had been built that were large enough to let us
see into the previously inaccessible "band of the computational
spectrum" that was our true target. My
later SPACERAM design generalized CAM8's
architecture into an almostideallyefficient buildingblock for
spatial SIMD computations and bitmapped virtual reality, but has not
yet been built.
My current research is again focused on theoretical questions at
the interface between physics and computation. A finite physical
system with finite energy has only a finite set of distinct (mutually
orthogonal) quantum states, and changes between distinct states at
only a finite rate. This
finitestate character makes all physical systems close kin to
digital computers, with fundamental physical quantities such as energy,
momentum and action being generalizations of
fundamental computing quantities. Time and space are effectively
discrete, because finite energy and momentum play the role of finite
bandwidth in ratelimiting distinctness in the quantum wavefunction.
Quantum uncertainty reflects a continuous description of discrete
quantities. Classical finitestate
models can play the same
foundational role in dynamics that they do in statistical
mechanics.
 Some of my papers:
Physics and Computation

PhysicsLike Models of Computation
(from 1984, in Physica D,
page 81).

Quantum Computation
(from 1986, in New Techniques and Ideas in Quantum Measurement
Theory, edited by Daniel Greenberger).

Physics and Computation
(from 1987, MIT PhD thesis).

Cellular Automata Machines
(with Toffoli, book published in 1987 by MIT Press).

Invertible Cellular Automata
(with Toffoli, from 1990, in Physica D, page 229).

Parallel quantum
computation (from 1990, in Complexity, Entropy, and the Physics
of Information, edited by Wojciech Zurek).

A Bridge of
Bits (from 1993, in Proceedings of the Workshop on Physics and
Computation, edited by Doug Matzke).

Elementary gates for quantum computation (with Barenco et. al, from 1995, in Physical Review A, page 3457).

The maximum speed of
dynamical evolution (with Levitin, from a conference in 1996, appears in
Physica D, page 188, 1998).

Crystalline
Computation (from 1999, in Feynman and Computation,
edited by Anthony Hey).
 Universal cellular
automata based on the collisions of soft spheres (from a
conference in 1999, appears in CollisionBased Computing,
edited by Andrew Adamatzky, page 107, 2002; and in New
Constructions in Cellular Automata, edited by David Griffeath and
Cristopher Moore, page 231, 2003).

Looking at Nature as a Computer
(from a workshop in 2001, appears in International Journal of
Theoretical Physics 42:2, page 309, 2003).
 Mechanical Systems that are
both Classical and Quantum (based on a talk given at the
Unconventional Computation Workshop, Santa Fe, March 22 2007). Roger
Critchlow turned one of the examples in this paper into a cute quantum/classical clock
demonstration in which the exact continuous motion of the clock's
hands is displayed
as a continuously evolving superposition of integertime states.

Quantum emulation of classical dynamics (2011, provides an isomorphism between classical finite state dynamics and quantum finiteenergy dynamics).

The ideal energy of
classical lattice dynamics (2015, uses bounds on distinct change
allowed by energy and momentum to define ideal energy and momentum for
finitestate classical systems).

The finitestate
character of physical dynamics (2017, relates discreteness in
space and time, and uncertainty, to the limitedbandwidth character
of finite energy and momentum).
Lattice Architectures

Cellularautomata supercomputers for fluid
dynamics modeling (with Toffoli and Vichniac, from 1986,
in Physical Review Letters, page 1694).

Cellular Automata Machines
(with Toffoli, book published in 1987 by MIT Press).

CAM8: a computer
architecture based on cellular automata
(from 1993, in Pattern Formation and LatticeGas Automata,
edited by A. Lawniczak and R. Kapral).
 An FPGA architecture
for DRAMbased systolic computations (from 1997, in Proceedings of
the IEEE Workshop on FPGAs for Custom Computing Machines, edited by
Arnold et. al., page 2).

An Embedded DRAM Architecture for
LargeScale SpatialLattice Computations (from 2000, in The 27th
Annual International Symposium on Computer Architecture, page 149).
 Mechanism for
efficient data access and communication in parallel computations on an
emulated spatial lattice (United States Patent 6,205,533
applied for in 1999, issued in 2001).
Lectures

Emulating
Physics: Cellular Automata that exhibit finitestate, locality,
invertibility and conservation laws
(a talk given at the Computing Beyond Silicon Summer
School, CalTech, June 24, 2002).

Physical
Worlds: Cellular Automata with computation universality at small and large scales
(a talk given at the Computing Beyond Silicon Summer
School, CalTech, June 25, 2002).

Spatial
Computers: Architectures and algorithms for largescale spatial computations
(a talk given at the Computing Beyond Silicon Summer
School, CalTech, June 26, 2002).

Nature as
Computer / Computer as Physics: Physical concepts enter Computer
Science and computer concepts enter Physics
(a talk given at the Computing Beyond Silicon Summer
School, CalTech, June 27, 2002).
Some Lattice Gas Movies
The models depicted in these movies are discussed above in the
paper "Crystalline Computation" and in the lecture "Emulating
Physics." All simulations were performed on CAM8.
 Diffusion and
sound waves in a reversible lattice gas (10MB): the four direction
TM lattice gas is started with a 50% density of particles, except for
an empty region (black) in the center. Half of the particles are
colored blue and half yellow, so that both diffusion and waves are
visible at the same time. The lattice is 512x512.
 Lattice gas fluid
flow (5MB): a simulation of a six direction lattice gas fluid
flowing past a half cylinder, exhibiting vortex shedding. Visualized
by also simulating a "smoke" fluid within the CA. System is 2Kx1K.
 "Slowtime"
model of refraction and reflection (5.7MB): blockpartitioning
version of invertible momentumconserving lattice gas, with particles
moving diagonally. Locations marked with blue are left unchanged in
half of the updates. We show a soliton colliding with a circular
slowtime region. The lattice is 512x512.
 Long range
forces in a lattice gas(3.5MB): a simulation of a six direction
lattice gas fluid with longrange forces. Force particles act at
three discrete distances to produce clumps that form an elastic
crystal. The model is discussed in A lattice
gas with long range interactions coupled to a heat bath (Yepez,
1993).
 A reversible model of
crystal growth (8MB): when a grey gas particle diffuses next to a
green crystal particle, it joins the crystal and emits a red heat
particle. The reverse also happens. The model is discussed in A thermodynamically
reversible generalization of diffusion limited aggregation (D'Souza and
Margolus, 1998).
 A cautionary tale...
email: nhm at mit.edu