Norman H. Margolus (born 1955) is a Canadian-American

physicist A physicist is a scientist who specializes in the field of physics, which encompasses the interactions of matter and energy at all length and time scales in the physical universe. Physicists generally are interested in the root or ultimate caus ...

and

computer scientist A computer scientist is a person who is trained in the academic study of computer science. Computer scientists typically work on the theoretical side of computation, as opposed to the hardware side on which computer engineers mainly focus (al ...

, known for his work on

cellular automata A cellular automaton (pl. cellular automata, abbrev. CA) is a discrete model of computation studied in automata theory. Cellular automata are also called cellular spaces, tessellation automata, homogeneous structures, cellular structures, tessel ...

and

reversible computing Reversible computing is any model of computation where the computational process, to some extent, is time-reversible. In a model of computation that uses deterministic transitions from one state of the abstract machine to another, a necessary c ...

.. He is a research affiliate with the

Computer Science and Artificial Intelligence Laboratory Computer Science and Artificial Intelligence Laboratory (CSAIL) is a research institute at the Massachusetts Institute of Technology (MIT) formed by the 2003 merger of the Laboratory for Computer Science (LCS) and the Artificial Intelligence Lab ...

at the

Massachusetts Institute of Technology The Massachusetts Institute of Technology (MIT) is a private land-grant research university in Cambridge, Massachusetts. Established in 1861, MIT has played a key role in the development of modern technology and science, and is one of the ...

Education and career

Margolus received his Ph.D. in physics in 1987 from the

(MIT) under the supervision of Edward Fredkin. He founded and was chief scientist for

Permabit Permabit Technology Corporation was a private supplier of Data Reduction solutions to the Computer Data Storage industry. On 31 July 2017 it was announced that Red Hat had acquired the assets and technology of Permabit Technology Corporation. Pe ...

, an information storage device company.

Research contributions

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 (sometimes spelled Moskito Island) is an island off the coast of Virgin Gorda and has long been a favourite for scuba divers and sailors. For many years the island was the location of a sail-in dive resort named Drake's Anchorag ...

in 1982. He is known for inventing the

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 (with different partitions at different time steps) and the transition rule ...

and the Margolus neighborhood for block cellular automata, which he used to develop cellular automaton simulations of

billiard-ball computer A billiard-ball computer, a type of 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. Instead of using electronic signals li ...

s.. Reprinted in . In the same work, Margolus also showed that the billiard ball model could be simulated by a

second-order cellular automaton A second-order cellular automaton is a type of reversible cellular automaton (CA) invented by Edward Fredkin. Reprinted in . where the state of a cell at time depends not only on its neighborhood at time , but also on its state at time .. Gen ...

, a different type of cellular automaton invented by his thesis advisor,

Edward Fredkin Edward Fredkin (born October 2, 1934) is a distinguished career professor at Carnegie Mellon University (CMU), and an early pioneer of digital physics. Fredkin's primary contributions include 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 Universal is the adjective for universe. Universal may also refer to: Companies * NBCUniversal, a media and entertainment company ** Universal Animation Studios, an American Animation studio, and a subsidiary of NBCUniversal ** Universal TV, a ...

(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 The Margolus–Levitin theorem states that the processing rate of all forms of computation (including quantum computation) cannot be higher than about 6 × 1033 operations per second per joule of energy. The theorem is named for Norman Margol ...

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 () is an Italian-American professor of electrical and computer engineering at Boston University where he joined the faculty in 1995. He has worked on cellular automata and the theory of artificial life (with Edward Fredkin and oth ...

, 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 An integrated circuit or monolithic integrated circuit (also referred to as an IC, a chip, or a microchip) is a set of electronic circuits on one small flat piece (or "chip") of semiconductor material, usually silicon. Large numbers of tiny ...

implementation of billiard-ball computation. He has also done pioneering research on the reversible

quantum gate In quantum computing and specifically the quantum circuit model of computation, a quantum logic gate (or simply quantum gate) is a basic quantum circuit operating on a small number of qubits. They are the building blocks of quantum circuits, lik ...

logic needed to support

quantum computer Quantum computing is a type of computation whose operations can harness the phenomena of quantum mechanics, such as superposition, interference, and entanglement. Devices that perform quantum computations are known as quantum computers. Though ...

s..

References

External links

Margolus' web site
at MIT {{DEFAULTSORT:Margolus, Norman 1955 births Living people American computer scientists 21st-century American physicists Cellular automatists MIT Department of Physics alumni University of Alberta alumni

Education and career

Research contributions

See also

References

External links