Artikel,

Undecidability and Intractability in Theoretical Physics

.
Phys. Rev. Lett., 54 (8): 735--738 (Februar 1985)
DOI: 10.1103/PhysRevLett.54.735

Zusammenfassung

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.

Tags

Nutzer

  • @ytyoun

Kommentare und Rezensionen