Norman Margolus

Norman H. Margolus (born 1955)^[1] is an Canadian-American^[2] physicist and computer scientist, known for his work on cellular automata and reversible computing.^[3] He is a research affiliate with the Computer Science and Artificial Intelligence Laboratory at the Massachusetts Institute of Technology.^[4]

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.^[5] 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 computers.^[3][6][7] 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);^[8] 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.^[9] 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.^[3][10][11]

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),^[3][12] and with Tom Knight he developed the "Flattop" integrated circuit implementation of billiard-ball computation.^[13] He has also done pioneering research on the reversible quantum gate logic needed to support quantum computers.^[14]

Margolus received his Ph.D. in physics in 1987 from MIT, under the supervision of Edward Fredkin.^[15] He founded and was chief scientist for Permabit, an information storage device company.^[16]

References

1. ^ Birth year as given in the index of Wolfram, Stephen (2002), A New Kind of Science, Wolfram Media, ISBN 1-57955-008-8 .
2. ^ He is described as Canadian in Wright, Robert (April 1988), "Did the Universe Just Happen?", The Atlantic Monthly, http://www.theatlantic.com/past/docs/issues/88apr/wright.htm .
3. ^ ^{a b c d} Brown, Julian (2002), Minds, Machines, and the Multiuniverse: The Quest for the Quantum Computer, Simon and Schuster, pp. 74–76, ISBN 9780743242639 .
4. ^ CSAIL directory, accessed 2011-02-03.
5. ^ Regis, Ed (1988), Who Got Einstein's Office?: Eccentricity and Genius at the Institute for Advanced Study, Basic Books, p. 239, ISBN 9780201122787 .
6. ^ Margolus, N. (1984), "Physics-like models of computation", Physica D 10: 81–95, doi:10.1016/0167-2789(84)90252-5 . Reprinted in Wolfram, Stephen, ed. (1986), Theory and Applications of Cellular Automata, Advanced series on complex systems, 1, World Scientific, pp. 232–246 .
7. ^ Schiff, Joel L. (2008), "4.2.1 Partitioning Cellular Automata", Cellular Automata: A Discrete View of the World, Wiley, pp. 115–116 .
8. ^ Fredkin, Edward, "Chapter 9: History", Introduction to Digital Philosophy (draft), http://www.digitalphilosophy.org/Home/Papers/TOC/Chapter9History/tabid/73/Default.aspx . A different mechanism for defining reversible universal cellular automata, by embedding d-dimensional irreversible automata into (d + 1)-dimensional reversible automata, was described earlier by Toffoli, Tommaso (1977), "Computation and construction universality of reversible cellular automata", Journal of Computer and System Sciences 15 (2): 213–231, http://pm1.bu.edu/~tt/qcl/pdf/toffolit197718176a6b.pdf .
9. ^ De Vos, Alexis (2010), Reversible Computing: Fundamentals, Quantum Computing, and Applications, Wiley, ISBN 9783527409921 .
10. ^ Margolus, Norman; Levitin, Lev B. (1998), "The maximum speed of dynamical evolution", Physica D 120: 188–195, arXiv:quant-ph/9710043, doi:10.1016/S0167-2789(98)00054-2 .
11. ^ Lloyd, Seth; Ng, Y. Jack (November, 2004), "Black Hole Computers", Scientific American: 53–61 .
12. ^ Ilachinski, Andrew (2001), "A.1.1 CAM-6", Cellular automata: a discrete universe, World Scientific, pp. 713–714, ISBN 9789812381835 .
13. ^ Johnson, George (June 15, 1999), "A Radical Computer Learns to Think in Reverse", New York Times, http://select.nytimes.com/gst/abstract.html?res=F60816FE3B5C0C768DDDAF0894D1494D81 .
14. ^ Barenco, Adriano; Bennett, Charles H.; Cleve, Richard; DiVincenzo, David P.; Margolus, Norman; Shor, Peter; Sleator, Tycho; Smolin, John A. et al. (1995), "Elementary gates for quantum computation", Physical Review A 52 (5): 3457–3467, doi:10.1103/PhysRevA.52.3457, PMID 9912645 .
15. ^ Margolus, Norman H. (1987), Physics and Computation, Ph.D. thesis, Massachusetts Institute of Technology, http://people.csail.mit.edu/nhm/thesis.pdf .
16. ^ Shread, Paul (October 27, 2003), "Permabit Makes a Case for CAS", Enterprise IT Planet, http://www.enterpriseitplanet.com/storage/news/article.php/3098981 .

External links

• Margolus' web site at MIT

Persondata
Name	Margolus, Norman
Alternative names
Short description
Date of birth	1955
Place of birth
Date of death
Place of death