DIMACS Theory Seminar

Title:

Fundamental physical limits on computation

Speaker:

Warren Smith

NEC Research

Place:

Room 402, Computer Science Building

Princeton University

Time:

Lunch 11:45 AM, Talk 12 Noon

Friday, May 5, 1995

Abstract:

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