COS 598c - Week 1

Week 1 (Feb. 2) Into the Kitchen

We start with something very concrete:

[Key88] R. W. Keyes, "Miniaturization of electronics and its limits," IBM J. Res. Develop. 32(1):24-28, January 1988.

I say concrete because this paper contains a collection of facts, more or less incontrovertible, about what are sometimes called "technology curves," as of about 1988. Of particular interest are the curves extrapolated to about 2010: number of atoms used to store a bit (Fig. 4), number of dopant impurities in the base of bipolar transistors (Fig. 5), and the energy dissipated per logic operation (Fig. 6).

Discussion Points

Can anyone update Figs. 4-6 to the present? Click here here for a plot of number of transistors on a die vs. time, from Peter Onufryk using data from the Semiconductor Industry Association.
Do you believe the general argument, or will solid-state electronics continue to improve performance forever in ways we can't imagine?
What does Keyes mean when he says, on p. 25,

"While Bennett's idea [reversible and dissipationless computation] has great conceptual significance... it is unlikely that it will be turned to practical advantage"?

At this point he references
R. Landauer, "Reversible Computation," Der Informationsbegriff in Technik und Wissenschaft, O. G. Folberth and C, Hackl (eds.), R. Oldenbourg, Munich, 1986, 139-158.
which I have yet to look up. How can it have great conceptual significance and not be exploitable?

This paper by Keyes points to two very important ideas: Landauer's kT lower bound on the cost of irreversible computation; and Bennett's demonstration, mentioned above, that computation can be performed reversibly. We will follow these pointers in the next few papers, starting with a somewhat general retrospective by Bennett that will set the stage for more detailed study:

[Ben88] C. H. Bennett, "Notes on the history of reversible computation", IBM J. Res. Develop., 32(1):16-23, January 1988.

A wonderful review of some very surprising twists and turns in scientific history, including what appears to be the best-yet exorcism of Maxwell's Demon, and the resolution of one-time controversial idea of reversible computation, and the origins of quantum computing. Bennett mentions loads of concepts that we will be studying and continually returning to.

Discussion Points

Make a list of all the ideas, results, concepts mentioned in this paper that you aren't 100% sure of.
Suppose there are small errors in the operation of Fredkin's billiard-ball model of computation? How many steps are possible until computation becomes unreliable?
It might be interesting, if somewhat ghoulish, to disinter "the erroneous proof that reversible cellular automata cannot be computational universal" (p. 19). Does Toffoli explain the bug in the proof?

This paper points directly to several papers that we will be reading either very soon, or later on.

Lest you get the impression that the developments described in this paper were received uncritically, we'll go back to a 1984 feature (news-like) article in Science that reveals not a little turmoil in the community:

[Rob84] Robinson, A. L., "Computing without dissipating energy", Science, 223:1164-1166, March 16, 1984.

I think it's interesting to look at this short piece from the sociological as well as the scientific point of view. It has the usual flavor of ``Science Reporting,'' and thus contains vague, and even incorrect, statements. (For example, the very first paragraph states that a reversible engine turns input energy into waste heat.) Typically, it also contains what appear to be quotes taken over the telephone, and aims at heightening the personal conflicts involved.

To be fair, it also lays out some fascinating issues in an entertaining way, and mentions scientific objections to the idea of reversible computation that need to be taken seriously. It might be a good term paper project to examine these objections: one by the Arizona State group in the 16 January 1984 Phys. Rev. Lett., another in Mead and Conway's classic textbook, and others that surely appear elsewhere in the literature.

We're next going to roll up our sleeve's, go back to Camelot, and look at Landauer's seminal 1961 paper.

I'll go over some classical information theory, especially the definition of information capacity as the logarithm of the number of states, and the derivation of entropy as the minimum capacity required to code a random source. There are then two other definitions of entropy: the S = integral dQ/T (from thermodynamics), and k*ln(# of distinguishable states) (from statistical mechanics). The Second Law of thermodynamics says that Delta S > 0 in a physical system (an empirical law).

What's New? | Master Reference List | Back to COS 598c front page | Back to General Information |