Aspects of Computability in Physics
arXiv:math/9711204
Abstract
This paper reviews connections between physics and computation, and explores their implications. The main topics are computational "hardness" of physical systems, computational status of fundamental theories, quantum computation, and the Universe as a computer.