Norm Margolus

I am a Research Affiliate at the MIT Computer Science and Artificial Intelligence Laboratory. I also consult for an Internet startup (Permabit) that I helped start.

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, 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, in addition to (and for a period instead of) more theoretical work on physics and on reversible cellular automata, I led the design and implementation of the CAM-8 CA machine, working closely with Tom Toffoli who led earlier CAM projects. CAM-8 was a spatially-organized mesh-architecture multiprocessor that provided a tool for investigating the possibilities of the kind of large-scale 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 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 CAM-8's architecture into an almost-ideally-efficient building-block for spatial SIMD computations and bit-mapped 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 finite character makes all physical systems close kin to digital computers, with fundamental physical quantities such as energy and momentum being generalizations of fundamental computing quantities. In fact, the mathematical machinery of hilbert spaces and hamiltonian dynamics provides a natural way to describe classical finite state systems using continuous time and space and sampling theory: this correspondence lets us regard quantum mechanics as a generalization of finite-state classical mechanics---in the same way that quantum computation is a generalization of classical computation.


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). 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 integer-time states.
Quantum emulation of classical dynamics (2011, provides an isomorphism between classical finite state dynamics and quantum finite-energy dynamics).
The maximum average rate of state change (2014, extends work on maximum speed of dynamics, includes momentum bound on spatial change).

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.
"Slow-time" model of refraction and reflection (5.7MB): block-partitioning version of invertible momentum-conserving 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 slow-time region. The lattice is 512x512.
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...

Superman 144 from Superman 144, April 1961

email: nhm at mit.edu