%0 Journal Article %1 wolfram85 %A Wolfram, Stephen %D 1985 %I American Physical Society %J Phys. Rev. Lett. %K np-hardness physics %N 8 %P 735--738 %R 10.1103/PhysRevLett.54.735 %T Undecidability and Intractability in Theoretical Physics %V 54 %X 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.

@article{wolfram85, 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.}, added-at = {2016-11-13T11:10:00.000+0100}, author = {Wolfram, Stephen}, biburl = {https://www.bibsonomy.org/bibtex/283ee95adefbdfcf3f0a93353b4a0b701/ytyoun}, doi = {10.1103/PhysRevLett.54.735}, interhash = {f817e273f2f79d66a7434e3af75386f0}, intrahash = {83ee95adefbdfcf3f0a93353b4a0b701}, journal = {Phys. Rev. Lett.}, keywords = {np-hardness physics}, month = feb, number = 8, numpages = {0}, pages = {735--738}, publisher = {American Physical Society}, timestamp = {2016-11-13T11:10:00.000+0100}, title = {Undecidability and Intractability in Theoretical Physics}, volume = 54, year = 1985 }