Norman Margolus
Encyclopedia
Norman H. Margolus is an Canadian-American physicist
and computer scientist
, known for his work on cellular automata
and reversible computing
. He is a research affiliate with the Computer Science and Artificial Intelligence Laboratory
at the Massachusetts Institute of Technology
.
Margolus was one of the organizers of a seminal research meeting on the connections between physics and computation theory, held on Mosquito Island
in 1982. He is known for inventing the block cellular automaton
and the Margolus neighborhood for block cellular automata, which he used to develop cellular automaton simulations of billiard-ball computer
s. In the same work, Margolus also showed that the billiard ball model could be simulated by a second order cellular automaton
, a different type of cellular automaton invented by his thesis advisor, Edward Fredkin
. These two simulations were among the first cellular automata that were both reversible (able to be run backwards as well as forwards for any number of time steps, without ambiguity) and universal
(able to simulate the operations of any computer program); this combination of properties is important in low-energy computing, as it has been shown that the energy dissipation of computing devices may be made arbitrarily small if and only if they are reversible. In connection with this issue, Margolus and his co-author Lev B. Levitin proved the Margolus–Levitin theorem showing that the speed of any computer is limited by the fundamental laws of physics to be at most proportional to its energy use; this implies that ultra-low-energy computers must run more slowly than conventional computers.
With Tommaso Toffoli
, Margolus developed the CAM-6
cellular automaton simulation hardware, which he extensively described in his book with Toffoli, Cellular Automata Machines (MIT Press, 1987), and with Tom Knight he developed the "Flattop" integrated circuit
implementation of billiard-ball computation. He has also done pioneering research on the reversible quantum gate
logic needed to support quantum computer
s.
Margolus received his Ph.D. in physics in 1987 from MIT, under the supervision of Edward Fredkin. He founded and was chief scientist for Permabit
, an information storage device company.
Physicist
A physicist is a scientist who studies or practices physics. Physicists study a wide range of physical phenomena in many branches of physics spanning all length scales: from sub-atomic particles of which all ordinary matter is made to the behavior of the material Universe as a whole...
and computer scientist
Computer scientist
A computer scientist is a scientist who has acquired knowledge of computer science, the study of the theoretical foundations of information and computation and their application in computer systems....
, known for his work on cellular automata
Cellular automaton
A cellular automaton is a discrete model studied in computability theory, mathematics, physics, complexity science, theoretical biology and microstructure modeling. It consists of a regular grid of cells, each in one of a finite number of states, such as "On" and "Off"...
and reversible computing
Reversible computing
Reversible computing is a model of computing where the computational process to some extent is reversible, i.e., time-invertible. A necessary condition for reversibility of a computational model is that the transition function mapping states to their successors at a given later time should be...
. He is a research affiliate with the Computer Science and Artificial Intelligence Laboratory
MIT Computer Science and Artificial Intelligence Laboratory
MIT Computer Science and Artificial Intelligence Laboratory is a research laboratory at the Massachusetts Institute of Technology formed by the 2003 merger of the Laboratory for Computer Science and Artificial Intelligence Laboratory...
at the Massachusetts Institute of Technology
Massachusetts Institute of Technology
The Massachusetts Institute of Technology is a private research university located in Cambridge, Massachusetts. MIT has five schools and one college, containing a total of 32 academic departments, with a strong emphasis on scientific and technological education and research.Founded in 1861 in...
.
Margolus was one of the organizers of a seminal research meeting on the connections between physics and computation theory, held on Mosquito Island
Mosquito Island
Mosquito Island is off the coast of Virgin Gorda and has long been a favourite for scuba divers and sailors. Sir Richard Branson purchased the island in 2007 for £10M...
in 1982. He is known for inventing the block cellular automaton
Block cellular automaton
A block cellular automaton or partitioning cellular automaton is a special kind of cellular automaton in which the lattice of cells is divided into non-overlapping blocks and the transition rule is applied to a whole block at a time rather than a single cell...
and the Margolus neighborhood for block cellular automata, which he used to develop cellular automaton simulations of billiard-ball computer
Billiard-Ball Computer
A billiard ball computer, also known as a conservative logic circuit, is an idealized model of a reversible mechanical computer based on newtonian dynamics, proposed in 1982 by Edward Fredkin and Tommaso Toffoli...
s. In the same work, Margolus also showed that the billiard ball model could be simulated by a second order cellular automaton
Second order cellular automaton
A second-order cellular automaton is a type of reversible cellular automaton invented by Edward Fredkin where the state of a cell at time depends not only on its neighborhood at time , but also on its state at time...
, a different type of cellular automaton invented by his thesis advisor, Edward Fredkin
Edward Fredkin
Edward Fredkin is an early pioneer of digital physics. In recent work, he uses the term digital philosophy . His primary contributions include his work on reversible computing and cellular automata...
. These two simulations were among the first cellular automata that were both reversible (able to be run backwards as well as forwards for any number of time steps, without ambiguity) and universal
Turing completeness
In computability theory, a system of data-manipulation rules is said to be Turing complete or computationally universal if and only if it can be used to simulate any single-taped Turing machine and thus in principle any computer. A classic example is the lambda calculus...
(able to simulate the operations of any computer program); this combination of properties is important in low-energy computing, as it has been shown that the energy dissipation of computing devices may be made arbitrarily small if and only if they are reversible. In connection with this issue, Margolus and his co-author Lev B. Levitin proved the Margolus–Levitin theorem showing that the speed of any computer is limited by the fundamental laws of physics to be at most proportional to its energy use; this implies that ultra-low-energy computers must run more slowly than conventional computers.
With Tommaso Toffoli
Tommaso Toffoli
Tommaso Toffoli is a professor of electrical and computer engineering at Boston University. He joined the faculty in 1995. He was born in June, 1943 in Montereale Valcellina, in northeastern Italy, and was raised in Rome. He received his doctorate in physics from the University of Rome La...
, Margolus developed the CAM-6
Cam-6
The CAM-6 accelerator is a PC-compatible expansion board designed to simulate cellular automata. It was designed by Tommaso Toffoli and Norman Margolus and is described at length in "Cellular Automata Machines", by Toffoli and Margolus ....
cellular automaton simulation hardware, which he extensively described in his book with Toffoli, Cellular Automata Machines (MIT Press, 1987), and with Tom Knight he developed the "Flattop" integrated circuit
Integrated circuit
An integrated circuit or monolithic integrated circuit is an electronic circuit manufactured by the patterned diffusion of trace elements into the surface of a thin substrate of semiconductor material...
implementation of billiard-ball computation. He has also done pioneering research on the reversible quantum gate
Quantum gate
In quantum computing and specifically the quantum circuit model of computation, a quantum gate is a basic quantum circuit operating on a small number of qubits. They are the building blocks of quantum circuits, like classical logic gates are for conventional digital circuits.Unlike many classical...
logic needed to support quantum computer
Quantum computer
A quantum computer is a device for computation that makes direct use of quantum mechanical phenomena, such as superposition and entanglement, to perform operations on data. Quantum computers are different from traditional computers based on transistors...
s.
Margolus received his Ph.D. in physics in 1987 from MIT, under the supervision of Edward Fredkin. He founded and was chief scientist for Permabit
Permabit
Permabit Technology Corporation, headquartered in Cambridge, MA, is a technology company that designs, builds and sells OEM-embedded data optimization software solutions and network-attached storage appliances targeted at enterprise archiving applications...
, an information storage device company.
External links
- Margolus' web site at MIT