Norman Margolus
I'm a Research Affiliate at the MIT Computer Science and Artificial
Intelligence Laboratory. I also provide some technical advice to
Permabit, an archival storage
company that I started.
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
1987, 12MB PDF) 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 I was also the Principal Investigator and leader of the CAM-8 CA machine
project, which designed and built a fine-grained,
spatially-organized mesh-architecture multiprocessor. The point of
this project was to advance the state of Cellular Automata modeling of
physics, by making available hardware that can take advantage of the
inherent efficiency of simple, uniform, spatially organized
computation. Software and algorithmic work using CAM-8 machines is
still ongoing at a number of locations, as well as architectural work
on next generation machines.
The CAM-8 project was intended to provide a tool for investigating
the possibilities of the kind of fine-grained parallelism that is
available in nature. It was successful in this, but the project ended
at the prototype stage, before CAM-8 machines had been built on a
scale sufficiently large to enable investigations into the "previously
inaccessible band of the computational spectrum" that was our true
target. Meanwhile, this project distracted me for several years from
pursuing fundamental questions in the Physical Theory of Computation.
Questions such as, What is the physical measure of the amount of
computation that a given dynamics can provide? How, in general, can
one construct relativistic cellular automata? How can one synchronize
the operation of quantum cellular automata? and What are the
Information-Mechanical generalizations of physical concepts such as
"action" and "least-action principles," in the context of CA models
that reproduce macroscopic physical phenomena? These are the research
topics that I am most interested in, though I still remain
fascinated by the possiblities of discrete lattice architectures.
- Some of my papers:
Physics and Lattice Gasses
Quantum Computation
(from 1986, in New Techniques and Ideas in Quantum Measurement
Theory, edited by Daniel Greenberger).
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).
The
maximum speed of dynamical evolution (from 1998, in Physica D,
page 188).
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 Collision Based Computation,
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).
Lattice Architectures
Cellular-automata supercomputers for
fluid dynamics modeling (from 1986, in Physical Review Letters,
page 1694).
CAM-8: a computer
architecture based on cellular automata
(from 1993, in Pattern Formation and Lattice-Gas Automata,
edited by A. Lawniczak and R. Kapral).
An FPGA architecture
for DRAM-based 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
Large-Scale Spatial-Lattice 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 finite-state, 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 large-scale 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 CAM-8.
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.
Long range
forces in a lattice gas(3.5MB): a simulation of a six direction
lattice gas fluid with long-range 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