Undecidability and Intractability in Theoretical Physics
.
Phys. Rev. Lett. 54 (8): 735--738 (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.
  • @ytyoun
This publication has not been reviewed yet.

rating distribution
average user rating0.0 out of 5.0 based on 0 reviews
    Please log in to take part in the discussion (add own reviews or comments).