Limits of computation

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.

Hardware limits or physical limits

Processing and memory density

• 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 the Bekenstein bound.^[1]

Processing speed

• 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.

Communication delays

• The
  Margolus–Levitin theorem sets a bound on the maximum computational speed per unit of energy: 6 × 10³³ operations per second per joule. This bound, however, can be avoided if there is access to quantum memory. Computational algorithms can then be designed that require arbitrarily small amounts of energy/time per one elementary computation step.^[2][3]

• cosmic microwave background radiation, without spending more energy on cooling than is saved in computation. However, on a timescale of 10⁹ – 10¹⁰ years, the cosmic microwave background radiation will be decreasing exponentially, which has been argued to eventually enable 10³⁰ as much computations per unit of energy.^[5] Important parts^{[clarification needed]} of this argument have been disputed.^[6]

• 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",^[7] which some have suggested might be used for computing purposes,^[8] 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
  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."^[10]
• In The Singularity Is Near, Ray Kurzweil cites the calculations of Seth Lloyd that a universal-scale computer is capable of 10⁹⁰ operations per second. The mass of the universe can be estimated at 3 × 10⁵² kilograms. If all matter in the universe was turned into a black hole, it would have a lifetime of 2.8 × 10¹³⁹ seconds before evaporating due to Hawking radiation. During that lifetime such a universal-scale black hole computer would perform 2.8 × 10²²⁹ operations.^[11]

Abstract limits in computer science

In the field of

classify the degree to which problems are respectively computable and computable in polynomial time. For instance, the level ${\displaystyle \Sigma _{0}^{0}=\Pi _{0}^{0}=\Delta _{0}^{0}}$ 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