Norman H. Margolus
Born1955
Other namesNorm Margolus
CitizenshipCanadian, American
Alma materMIT
Known forMargolus neighborhood
Margolus gate
Margolus–Levitin theorem
Block cellular automaton
Reversible cellular automaton
CAM-6 accelerator
Computronium
Critters
Scientific career
FieldsComputer Science, Cellular Automata
Websitehttps://people.csail.mit.edu/nhm/

Norman H. Margolus (born 1955)[1] is a 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]

Education and career

Margolus received his Ph.D. in physics in 1987 from the Massachusetts Institute of Technology (MIT) under the supervision of Edward Fredkin.[5] He founded and was chief scientist for Permabit, an information storage device company.[6]

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 in 1982.[7] 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][8][9]

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);[10] 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.[11]

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][12][13]

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

See also

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.
  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 978-0-7432-4263-9.
  4. ^ CSAIL directory Archived 2011-04-26 at the Wayback Machine, accessed 2011-02-03.
  5. ^ Margolus, Norman H. (1987), Physics and Computation (PDF), Ph.D. thesis, Massachusetts Institute of Technology.
  6. ^ Shread, Paul (October 27, 2003), "Permabit Makes a Case for CAS", Enterprise IT Planet.
  7. ^ Regis, Ed (1988), Who Got Einstein's Office?: Eccentricity and Genius at the Institute for Advanced Study, Basic Books, p. 239, ISBN 978-0-201-12278-7.
  8. ^ Margolus, N. (1984), "Physics-like models of computation", Physica D, 10 (1–2): 81–95, Bibcode:1984PhyD...10...81M, 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, vol. 1, World Scientific, pp. 232–246, Bibcode:1986taca.book.....W.
  9. ^ Schiff, Joel L. (2008), "4.2.1 Partitioning Cellular Automata", Cellular Automata: A Discrete View of the World, Wiley, pp. 115–116.
  10. ^ Fredkin, Edward, "Chapter 9: History", Introduction to Digital Philosophy (draft), archived from the original on 2012-04-15. 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" (PDF), Journal of Computer and System Sciences, 15 (2): 213–231, doi:10.1016/s0022-0000(77)80007-x.
  11. ^ De Vos, Alexis (2010), Reversible Computing: Fundamentals, Quantum Computing, and Applications, Wiley, ISBN 978-3-527-40992-1.
  12. ^ Margolus, Norman; Levitin, Lev B. (1998), "The maximum speed of dynamical evolution", Physica D, 120 (1–2): 188–195, arXiv:quant-ph/9710043, Bibcode:1998PhyD..120..188M, doi:10.1016/S0167-2789(98)00054-2, S2CID 468290.
  13. ^ Lloyd, Seth; Ng, Y. Jack (November 2004), "Black Hole Computers", Scientific American, 291 (5): 53–61, Bibcode:2004SciAm.291e..52L, doi:10.1038/scientificamerican1104-52, PMID 15521147.
  14. ^ Ilachinski, Andrew (2001), "A.1.1 CAM-6", Cellular automata: a discrete universe, World Scientific, pp. 713–714, ISBN 978-981-238-183-5.
  15. ^ Johnson, George (June 15, 1999), "A Radical Computer Learns to Think in Reverse", New York Times.
  16. ^ Barenco, Adriano; Bennett, Charles H.; Cleve, Richard; DiVincenzo, David P.; Margolus, Norman; Shor, Peter; Sleator, Tycho; Smolin, John A.; Weinfurter, Harald (1995), "Elementary gates for quantum computation", Physical Review A, 52 (5): 3457–3467, arXiv:quant-ph/9503016, Bibcode:1995PhRvA..52.3457B, doi:10.1103/PhysRevA.52.3457, PMID 9912645, S2CID 8764584.

External links

Authority control databases
Categories