World Library  
Flag as Inappropriate
Email this Article

Limits to computation

Article Id: WHEBN0002855255
Reproduction Date:

Title: Limits to computation  
Author: World Heritage Encyclopedia
Language: English
Subject: Physics of computation, Koomey's law, Landauer's principle, Bekenstein bound, Theory of computation
Collection: Theory of Computation
Publisher: World Heritage Encyclopedia

Limits to computation


  • Physical limits 1
  • Building devices that approach physical limits 2
  • Abstract limits in Computer Science 3
  • Loose and tight limits 4
  • See also 5
  • References 6

Physical limits

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:

  • The Bekenstein bound limits the amount of information that can be stored within a spherical volume to the entropy of a black hole with the same surface area.
  • Thermodynamics limit the data storage of a system based on its energy, number of particles and particle modes. In practice it is a stronger bound than Bekenstein bound.[1]
  • The temperature of the cosmic microwave background radiation gives a practical lower limit to the energy consumed to perform computation of approximately ln(2) kT per irreversible state change, where k is the Boltzmann constant and T is the temperature of the background (about 3 kelvins). While a device could be cooled to operate below this temperature, the energy expended by the cooling would offset the benefit of the lower operating temperature.
  • Bremermann's limit is the maximum computational speed of a self-contained system in the material universe, and is based on mass-energy versus quantum uncertainty constraints.
  • Margolus–Levitin theorem sets a bound on the maximum computational speed per unit of energy: 6 × 1033 operations per second per joule.
  • Landauer's principle is a physical principle pertaining to the lower theoretical limit of energy consumption of a computation.
  • Schlock's law is a concept developed after the Rangel curve bound of level computation which governs the levels of "k" in an open system of any calculation where the Boltzmann constant must be applied to determine maximum computational speed.

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:

  • A cold degenerate star could conceivably be used as a giant data storage device, by carefully perturbing it to various excited states, in the same manner as an atom or quantum well used for these purposes. Such a star would have to be artificially constructed, as no natural degenerate stars will cool to this temperature for an extremely long time. It is also possible that nucleons on the surface of neutron stars could form complex "molecules"[2] which some have suggested might be used for computing purposes,[3] creating a type of computronium based on femtotechnology which would be faster and denser than computronium based on nanotechnology.
  • It may be possible to use a black hole as a data storage and/or computing device, if a practical mechanism for extraction of contained information can be found. Such extraction may in principle be possible (Stephen Hawking's proposed resolution to the black hole information paradox). This would achieve storage density exactly equal to the Bekenstein Bound. Professor Seth Lloyd calculated the computational abilities of an "ultimate laptop" formed by compressing a kilogram of matter into a black hole of radius 1.485 × 10−27 meters, concluding that it would only last about 10−19 seconds before evaporating due to Hawking radiation, but that during this brief time it could compute at a rate of about 5 × 1050 operations per second, ultimately performing about 1032 operations on 1016 bits (~1 PB). Lloyd notes that "Interestingly, although this hypothetical computation is performed at ultra-high densities and speeds, the total number of bits available to be processed is not far from the number available to current computers operating in more familiar surroundings."[4]

Abstract limits in Computer Science

Computer Science studies abstract models of computation, for which it considers various computational tasks and notions of solving them. For example, some tasks, such as undecidable problems, cannot be solved in principle. Others, NP-hard tasks cannot be solved quickly and accurately in all cases. Some tasks appear difficult to paralellize. These categories of tasks are called complexity classes and a large number of them have been classified and compared to each other. Some classes, defined in different ways, may coincide - providing a conclusive answer to such questions is a common pattern for unsolved challenges in Computer Science (see the P vs. NP challenge).

Loose and tight limits

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

See also


  1. ^ Sandberg, Anders (22 December 1999). "The Physics of Information Processing Superobjects: Daily Life Among the Jupiter Brains" (PDF). 
  2. ^ "Life on neutron stars". The Internet Encyclopedia of Science. 
  3. ^ Femtotech? (Sub)Nuclear Scale Engineering and Computation at the Wayback Machine (archived October 25, 2004)
  4. ^ Lloyd, Seth (2000). "Ultimate physical limits to computation" (PDF).  
  5. ^ Markov, Igor (2014). "Limits on Fundamental Limits to Computation".  
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Copyright © World Library Foundation. All rights reserved. eBooks from World Library are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.