Abstract

Physical processes are viewed as computations, and the difficulty of answering questions about them is characterized in terms of the difficulty of performing the corresponding computations. Cellular automata are used to provide explicit examples of various formally undecidable and computationally intractable problems. It is suggested that such problems are common in physical models, and some other potential examples are discussed.

next