Phys. Rev. Lett. 54, 735–738 (1985)Undecidability and intractability in theoretical physicsReceived 26 October 1984; published in the issue dated 25 February 1985 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. © 1985 The American Physical Society URL:
http://link.aps.org/doi/10.1103/PhysRevLett.54.735
DOI:
10.1103/PhysRevLett.54.735
PACS:
02.90.+p, 01.70.+w, 05.90.+m
|
|
About | Terms and Conditions | Subscriptions | Search | Help
Use of the American Physical Society websites and journals implies that the user has read and agrees to our Terms and Conditions and any applicable Subscription Agreement. Physical Review®, Physical Review Letters®, Reviews of Modern Physics®, and Physical Review Special Topics® are trademarks of the American Physical Society.