Limits of computation

Last updated

The limits of computation are governed by a number of different factors. In particular, there are several physical and practical limits to the amount of computation or data storage that can be performed with a given amount of mass, volume, or energy.

Contents

Hardware limits or physical limits

Processing and memory density

Processing speed

Communication delays

Energy supply

Building devices that approach physical limits

Several methods have been proposed for producing computing devices or data storage devices that approach physical and practical limits:

Abstract limits in computer science

In the field of theoretical computer science the computability and complexity of computational problems are often sought-after. Computability theory describes the degree to which problems are computable, whereas complexity theory describes the asymptotic degree of resource consumption. Computational problems are therefore confined into complexity classes. The arithmetical hierarchy and polynomial hierarchy classify the degree to which problems are respectively computable and computable in polynomial time. For instance, the level of the arithmetical hierarchy classifies computable, partial functions. Moreover, this hierarchy is strict such that at any other class in the arithmetic hierarchy classifies strictly uncomputable functions.

Loose and tight limits

Many limits derived in terms of physical constants and abstract models of computation in computer science are loose. [12] Very few known limits directly obstruct leading-edge technologies, but many engineering obstacles currently cannot be explained by closed-form limits.

See also

References

  1. Sandberg, Anders (22 December 1999). "The Physics of Information Processing Superobjects: Daily Life Among the Jupiter Brains" (PDF). Journal of Evolution and Technology. Archived from the original (PDF) on 5 March 2015. Retrieved 30 May 2014.
  2. Jordan, Stephen P. (2017). "Fast quantum computation at arbitrarily low energy". Phys. Rev. A. 95 (3) 032305. arXiv: 1701.01175 . Bibcode:2017PhRvA..95c2305J. doi:10.1103/physreva.95.032305. S2CID   118953874.
  3. Sinitsyn, Nikolai A. (2018). "Is there a quantum limit on speed of computation?". Physics Letters A. 382 (7): 477–481. arXiv: 1701.05550 . Bibcode:2018PhLA..382..477S. doi:10.1016/j.physleta.2017.12.042. S2CID   55887738.
  4. Vitelli, M.B.; Plenio, V. (2001). "The physics of forgetting: Landauer's erasure principle and information theory" (PDF). Contemporary Physics. 42 (1): 25–60. arXiv: quant-ph/0103108 . Bibcode:2001ConPh..42...25P. doi:10.1080/00107510010018916. eISSN   1366-5812. hdl:10044/1/435. ISSN   0010-7514. S2CID   9092795.
  5. Sandberg, Anders; Armstrong, Stuart; Cirkovic, Milan M. (2017-04-27). "That is not dead which can eternal lie: the aestivation hypothesis for resolving Fermi's paradox". arXiv: 1705.03394 [physics.pop-ph].
  6. Bennett, Charles H.; Hanson, Robin; Riedel, C. Jess (1 August 2019). "Comment on 'The Aestivation Hypothesis for Resolving Fermi's Paradox'". Foundations of Physics. 49 (8): 820–829. arXiv: 1902.06730 . Bibcode:2019FoPh...49..820B. doi:10.1007/s10701-019-00289-5. ISSN   1572-9516. S2CID   119045181.
  7. "Life on neutron stars". The Internet Encyclopedia of Science.
  8. "Femtotech? (Sub)Nuclear Scale Engineering and Computation". Archived from the original on October 25, 2004. Retrieved October 30, 2006.
  9. Lloyd, Seth (2000). "Ultimate physical limits to computation". Nature. 406 (6799): 1047–1054. arXiv: quant-ph/9908043 . Bibcode:2000Natur.406.1047L. doi:10.1038/35023282. PMID   10984064. S2CID   75923.
  10. Lloyd, Seth (2000). "Ultimate physical limits to computation" (PDF). Nature . 406 (6799): 1047–1054. arXiv: quant-ph/9908043 . Bibcode:2000Natur.406.1047L. doi:10.1038/35023282. PMID   10984064. S2CID   75923. Archived from the original (PDF) on August 7, 2008.
  11. Kurzweil, Ray (2005). The Singularity is Near. New York: Viking. p. 911.{{cite book}}: CS1 maint: publisher location (link)
  12. Markov, Igor (2014). "Limits on Fundamental Limits to Computation". Nature . 512 (7513): 147–154. arXiv: 1408.3821 . Bibcode:2014Natur.512..147M. doi:10.1038/nature13570. PMID   25119233. S2CID   4458968.