Abstract

Computation is a physical process, inevitably utilizing physical degrees of freedom. Computation, therefore, is restricted by the laws of physics and also by the construction materials and operating environments available in our actual universe. These restrictions have been investigated for a quarter century. A discussion of this field is provided, too concise to be a review, but only intended as a guide to the literature. Physical law, in turn, consists of algorithms for information processing. Therefore, the ultimate form of physical laws must be consistent with the restrictions on the physical executability of algorithms, which is in turn dependent on physical law