DIMACS Theory Seminar


Fundamental physical limits on computation


Warren Smith
NEC Research


Room 402, Computer Science Building
Princeton University


Lunch 11:45 AM, Talk 12 Noon
Friday, May 5, 1995


We consider limitations on the performance of computers arising from thermodynamics and the laws of physics. We provide upper bounds on three quantities: sustained information flux, information storage density, and sustained computational speed. All of these upper bounds are ``tight'' in the sense that they could be approached by plausible-sounding physical systems, and they all arise from a single unified point of view. We also make a conjecture about the rate of inevitable decay of stored information. This conjecture may be thought of as a quantitative extension of the second law of thermodynamics. It leads to a bound on the density of stable information. We carefully elucidate the assumptions behind these bounds. We give a list of 4 open problems at the end.

Host: Sanjeev Arora

Document last modified on May 1, 1995