Undecidability and intractability in theoretical physics
- 25 February 1985
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review Letters
- Vol. 54 (8) , 735-738
- https://doi.org/10.1103/physrevlett.54.735
Abstract
Physical Processes are reviewed 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.Keywords
This publication has 11 references indexed in Scilit:
- Cellular automata as models of complexityNature, 1984
- Entropy content and information flow in systems with limited energyPhysical Review D, 1984
- Computer Software in Science and MathematicsScientific American, 1984
- Equivalence of Cellular Automata to Ising Models and Directed PercolationPhysical Review Letters, 1984
- Computation theory of cellular automataCommunications in Mathematical Physics, 1984
- Optimization by Simulated AnnealingScience, 1983
- The thermodynamics of computation—a reviewInternational Journal of Theoretical Physics, 1982
- On the computational complexity of Ising spin glass modelsJournal of Physics A: General Physics, 1982
- Conservative logicInternational Journal of Theoretical Physics, 1982
- Undecidability and nonperiodicity for tilings of the planeInventiones Mathematicae, 1971