219:(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.
226:
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.
887:
215:. 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
161:
536:
877:
192:
Margolus was one of the organizers of a seminal research meeting on the connections between physics and computation theory, held on
768:
373:
892:
872:
730:
607:
447:
355:
177:
165:
544:
747:
200:
and the
Margolus neighborhood for block cellular automata, which he used to develop cellular automaton simulations of
301:
208:
64:
882:
92:
80:
223:
72:
68:
412:
250:
implementation of billiard-ball computation. He has also done pioneering research on the reversible
197:
76:
238:
cellular automaton simulation hardware, which he extensively described in his book with
Toffoli,
439:
432:
319:
867:
243:
201:
292:
207:
In the same work, Margolus also showed that the billiard ball model could be simulated by a
862:
802:
687:
642:
498:
472:
324:
157:
549:. A different mechanism for defining reversible universal cellular automata, by embedding
8:
678:
563:
267:
216:
806:
691:
646:
502:
476:
826:
792:
658:
632:
497:, Advanced series on complex systems, vol. 1, World Scientific, pp. 232–246,
434:
Who Got
Einstein's Office?: Eccentricity and Genius at the Institute for Advanced Study
247:
153:
149:
699:
654:
623:
Margolus, Norman; Levitin, Lev B. (1998), "The maximum speed of dynamical evolution",
583:
180:(MIT) under the supervision of Edward Fredkin. He founded and was chief scientist for
818:
726:
703:
603:
484:
443:
351:
297:
222:
In connection with this issue, Margolus and his co-author Lev B. Levitin proved the
830:
810:
695:
650:
578:
480:
370:
255:
662:
559:
490:
377:
287:
231:
193:
780:
752:
532:
212:
856:
814:
772:
391:
707:
564:"Computation and construction universality of reversible cellular automata"
251:
88:
822:
557: + 1)-dimensional reversible automata, was described earlier by
348:
Minds, Machines, and the
Multiuniverse: The Quest for the Quantum Computer
797:
783:; Weinfurter, Harald (1995), "Elementary gates for quantum computation",
637:
211:, a different type of cellular automaton invented by his thesis advisor,
776:
600:
Reversible
Computing: Fundamentals, Quantum Computing, and Applications
145:
122:
846:
181:
676:
Lloyd, Seth; Ng, Y. Jack (November 2004), "Black Hole
Computers",
516:
Schiff, Joel L. (2008), "4.2.1 Partitioning
Cellular Automata",
888:
Massachusetts
Institute of Technology School of Science alumni
766:
235:
84:
463:
Margolus, N. (1984), "Physics-like models of computation",
176:
Margolus received his Ph.D. in physics in 1987 from the
162:
Computer
Science and Artificial Intelligence Laboratory
399:, Ph.D. thesis, Massachusetts Institute of Technology
431:
16:Canadian-American physicist and computer scientist
854:
748:"A Radical Computer Learns to Think in Reverse"
622:
518:Cellular Automata: A Discrete View of the World
495:Theory and Applications of Cellular Automata
775:; DiVincenzo, David P.; Margolus, Norman;
721:Ilachinski, Andrew (2001), "A.1.1 CAM-6",
720:
541:Introduction to Digital Philosophy (draft)
796:
636:
582:
553:-dimensional irreversible automata into (
187:
184:, an information storage device company.
462:
389:
745:
675:
571:Journal of Computer and System Sciences
558:
489:
286:
196:in 1982. He is known for inventing the
171:
855:
725:, World Scientific, pp. 713–714,
723:Cellular automata: a discrete universe
597:
515:
410:
350:, Simon and Schuster, pp. 74–76,
317:
160:. He is a research affiliate with the
429:
345:
341:
339:
337:
335:
178:Massachusetts Institute of Technology
166:Massachusetts Institute of Technology
285:Birth year as given in the index of
531:
144:(born 1955) is a Canadian-American
109:Computer Science, Cellular Automata
13:
456:
332:
14:
904:
840:
746:Johnson, George (June 15, 1999),
700:10.1038/scientificamerican1104-52
411:Shread, Paul (October 27, 2003),
878:21st-century American physicists
760:
739:
714:
669:
616:
591:
525:
413:"Permabit Makes a Case for CAS"
320:"Did the Universe Just Happen?"
316:He is described as Canadian in
209:second-order cellular automaton
509:
423:
404:
383:
364:
310:
279:
1:
655:10.1016/S0167-2789(98)00054-2
584:10.1016/s0022-0000(77)80007-x
318:Wright, Robert (April 1988),
273:
81:Reversible cellular automaton
893:University of Alberta alumni
873:American computer scientists
485:10.1016/0167-2789(84)90252-5
390:Margolus, Norman H. (1987),
242:(MIT Press, 1987), and with
7:
261:
246:he developed the "Flattop"
32:1955 (age 68–69)
10:
909:
240:Cellular Automata Machines
520:, Wiley, pp. 115–116
234:, Margolus developed the
117:
113:
105:
98:
60:
52:
44:
36:
28:
21:
815:10.1103/PhysRevA.52.3457
254:logic needed to support
224:Margolus–Levitin theorem
198:block cellular automaton
152:, known for his work on
77:Block cellular automaton
73:Margolus–Levitin theorem
598:De Vos, Alexis (2010),
438:, Basic Books, p.
393:Physics and Computation
202:billiard-ball computers
380:, accessed 2011-02-03.
346:Brown, Julian (2002),
188:Research contributions
293:A New Kind of Science
65:Margolus neighborhood
883:Cellular automatists
537:"Chapter 9: History"
417:Enterprise IT Planet
325:The Atlantic Monthly
172:Education and career
158:reversible computing
807:1995PhRvA..52.3457B
769:Bennett, Charles H.
692:2004SciAm.291e..52L
679:Scientific American
647:1998PhyD..120..188M
503:1986taca.book.....W
477:1984PhyD...10...81M
268:Programmable matter
847:Margolus' web site
779:; Sleator, Tycho;
767:Barenco, Adriano;
430:Regis, Ed (1988),
376:2011-04-26 at the
248:integrated circuit
150:computer scientist
142:Norman H. Margolus
48:Canadian, American
23:Norman H. Margolus
785:Physical Review A
732:978-981-238-183-5
609:978-3-527-40992-1
449:978-0-201-12278-7
357:978-0-7432-4263-9
296:, Wolfram Media,
256:quantum computers
154:cellular automata
139:
138:
100:Scientific career
85:CAM-6 accelerator
900:
835:
833:
800:
798:quant-ph/9503016
791:(5): 3457–3467,
764:
758:
756:
743:
737:
735:
718:
712:
710:
673:
667:
665:
640:
638:quant-ph/9710043
631:(1–2): 188–195,
620:
614:
612:
595:
589:
587:
586:
568:
560:Toffoli, Tommaso
548:
543:, archived from
529:
523:
521:
513:
507:
505:
491:Wolfram, Stephen
487:
460:
454:
452:
437:
427:
421:
419:
408:
402:
400:
398:
387:
381:
368:
362:
360:
343:
330:
328:
314:
308:
306:
288:Wolfram, Stephen
283:
135:
132:
130:
128:
126:
124:
37:Other names
19:
18:
908:
907:
903:
902:
901:
899:
898:
897:
853:
852:
843:
838:
781:Smolin, John A.
765:
761:
744:
740:
733:
719:
715:
674:
670:
621:
617:
610:
596:
592:
566:
533:Fredkin, Edward
530:
526:
514:
510:
488:. Reprinted in
461:
457:
450:
428:
424:
409:
405:
396:
388:
384:
378:Wayback Machine
371:CSAIL directory
369:
365:
358:
344:
333:
315:
311:
304:
284:
280:
276:
264:
232:Tommaso Toffoli
194:Mosquito Island
190:
174:
121:
91:
87:
83:
79:
75:
71:
67:
53:Alma mater
24:
17:
12:
11:
5:
906:
896:
895:
890:
885:
880:
875:
870:
865:
851:
850:
842:
841:External links
839:
837:
836:
773:Cleve, Richard
759:
753:New York Times
738:
731:
713:
668:
615:
608:
590:
577:(2): 213–231,
524:
508:
493:, ed. (1986),
471:(1–2): 81–95,
455:
448:
422:
403:
382:
363:
356:
331:
309:
302:
277:
275:
272:
271:
270:
263:
260:
213:Edward Fredkin
189:
186:
173:
170:
137:
136:
119:
115:
114:
111:
110:
107:
103:
102:
96:
95:
62:
61:Known for
58:
57:
54:
50:
49:
46:
42:
41:
38:
34:
33:
30:
26:
25:
22:
15:
9:
6:
4:
3:
2:
905:
894:
891:
889:
886:
884:
881:
879:
876:
874:
871:
869:
868:Living people
866:
864:
861:
860:
858:
848:
845:
844:
832:
828:
824:
820:
816:
812:
808:
804:
799:
794:
790:
786:
782:
778:
774:
770:
763:
755:
754:
749:
742:
734:
728:
724:
717:
709:
705:
701:
697:
693:
689:
685:
681:
680:
672:
664:
660:
656:
652:
648:
644:
639:
634:
630:
626:
619:
611:
605:
601:
594:
585:
580:
576:
572:
565:
561:
556:
552:
547:on 2012-04-15
546:
542:
538:
534:
528:
519:
512:
504:
500:
496:
492:
486:
482:
478:
474:
470:
466:
459:
451:
445:
441:
436:
435:
426:
418:
414:
407:
395:
394:
386:
379:
375:
372:
367:
359:
353:
349:
342:
340:
338:
336:
327:
326:
321:
313:
305:
303:1-57955-008-8
299:
295:
294:
289:
282:
278:
269:
266:
265:
259:
257:
253:
249:
245:
241:
237:
233:
228:
225:
220:
218:
214:
210:
205:
203:
199:
195:
185:
183:
179:
169:
167:
163:
159:
155:
151:
147:
143:
134:
120:
116:
112:
108:
104:
101:
97:
94:
90:
86:
82:
78:
74:
70:
69:Margolus gate
66:
63:
59:
55:
51:
47:
43:
40:Norm Margolus
39:
35:
31:
27:
20:
788:
784:
762:
751:
741:
722:
716:
686:(5): 53–61,
683:
677:
671:
628:
624:
618:
599:
593:
574:
570:
554:
550:
545:the original
540:
527:
517:
511:
494:
468:
464:
458:
433:
425:
416:
406:
392:
385:
366:
347:
323:
312:
291:
281:
252:quantum gate
239:
229:
221:
206:
191:
175:
141:
140:
99:
89:Computronium
863:1955 births
777:Shor, Peter
45:Citizenship
857:Categories
274:References
244:Tom Knight
625:Physica D
602:, Wiley,
465:Physica D
217:universal
146:physicist
708:15521147
562:(1977),
374:Archived
290:(2002),
262:See also
182:Permabit
93:Critters
831:8764584
823:9912645
803:Bibcode
688:Bibcode
643:Bibcode
499:Bibcode
473:Bibcode
164:at the
118:Website
849:at MIT
829:
821:
729:
706:
663:468290
661:
606:
446:
354:
300:
125:.csail
123:people
106:Fields
827:S2CID
793:arXiv
659:S2CID
633:arXiv
567:(PDF)
397:(PDF)
236:CAM-6
230:With
819:PMID
727:ISBN
704:PMID
604:ISBN
444:ISBN
352:ISBN
298:ISBN
156:and
148:and
131:/nhm
129:.edu
127:.mit
29:Born
811:doi
696:doi
684:291
651:doi
629:120
579:doi
481:doi
440:239
204:.
56:MIT
859::
825:,
817:,
809:,
801:,
789:52
787:,
771:;
750:,
702:,
694:,
682:,
657:,
649:,
641:,
627:,
575:15
573:,
569:,
539:,
535:,
479:,
469:10
467:,
442:,
415:,
334:^
322:,
258:.
168:.
834:.
813::
805::
795::
757:.
736:.
711:.
698::
690::
666:.
653::
645::
635::
613:.
588:.
581::
555:d
551:d
522:.
506:.
501::
483::
475::
453:.
420:.
401:.
361:.
329:.
307:.
133:/
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.