CIS 4930.1194X/6930.1078X
Spr.'00
Assignment #9 (Course Part VII, Weeks 13-14):
Physical Models of Computation
Please continue to follow the general
advice on reading assignments from the
first week's assignment. Slides for this section's lectures will
be placed on reserve when available.
Reading assignment:
The topic for these two weeks is on the concept of developing models of
computation that are in perfect accordance with the computational capabilities
of physics itself (insofar as we know them), so as to provide the most
appropriate model for analyzing the efficiency of algorithms.
For now, the readings for this part of the course are just the following
sections of "Reversibility for Efficient Computing":
-
Sections 3.1, "Models of computation," and 3.2, "Computational complexity
and efficiency" (pp. 52-59) of course
manuscript.
-
Chapter 5, "Ultimate physical models of computation," pp. 107-120 of course
manuscript.
-
Chapter 6, "Reversibility and physical scaling laws," pp. 121-143 of course
manuscript.
-
Chapter 8, "Future reversible device technologies," pp. 215-223 of course
manuscript.
If you like, you can also read the following relevant published articles,
although they are pretty much redundant with what's in the course manuscript.
-
Michael P. Frank and Tom Knight, ``Ultimate Theoretical Models of Nanocomputers,''
Nanotechnology9(3):162-176,
Sep. 1998. Also presented at the Fifth Foresight Conference on Molecular
Nanotechnology, Palo Alto, CA, Nov. 1997. http://www.ai.mit.edu/~mpf/Nano97/paper.html.
-
Michael P. Frank, Tom Knight, Norm Margolus, ``Reversibility in optimal
scalable computer architectures,'' in Calude, Casti, Dineen, eds., Unconventional
Models of Computation (proceedings of the First International Conference
on Unconventional Models of Computation, Jan. 1998), pages 165-182, Springer,
1998. http://www.ai.mit.edu/~mpf/rc/scaling_paper/scaling.html.
Bonus Material:
This is material that was covered after the originally-scheduled course
material was finished. The topics were Public-Key cryptography, the
RSA cryptosystem, and ...
Written assignment #9: (due Mon. 4/24)
This is our standing written assignment. It should be on the subject
of the above lectures and reading material. If you wish, you may
also write about Fredkin's guest lecture on Digital Mechanics. This
assignment #9 may be skipped if you are doing the extra
credit project.