View source for Limits of computation

{{Short description|Overview of the 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.<ref>{{cite journal|last=Sandberg|first=Anders|title=The Physics of Information Processing Superobjects: Daily Life Among the Jupiter Brains|date=22 December 1999|url=http://transhumanist.com/volume5/Brains2.pdf|access-date=30 May 2014|archive-url=https://web.archive.org/web/20150305173119/http://www.transhumanist.com/volume5/Brains2.pdf|archive-date=5 March 2015|url-status=dead|journal=Journal of Evolution and Technology}}</ref>

=== 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 equivalence|mass–energy]] versus [[Uncertainty principle|quantum uncertainty]] constraints.

=== Communication delays ===
* The [[Margolus–Levitin theorem]] sets a bound on the maximum computational speed per unit of energy: 6 &times; 10<sup>33</sup> 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.<ref>{{cite journal|last=Jordan|first=Stephen P.|title=Fast quantum computation at arbitrarily low energy|journal = Phys. Rev. A | volume = 95 |issue=3| pages=032305 | year=2017 |arxiv = 1701.01175| doi=10.1103/physreva.95.032305|bibcode=2017PhRvA..95c2305J|s2cid=118953874}}</ref><ref>{{cite journal|last=Sinitsyn|first=Nikolai A.|title=Is there a quantum limit on speed of computation?|journal=Physics Letters A|volume=382|issue=7|pages=477–481|year=2018|arxiv = 1701.05550|bibcode=2018PhLA..382..477S|doi=10.1016/j.physleta.2017.12.042|s2cid=55887738}}</ref>

=== Energy supply ===
* [[Landauer's principle]] defines a lower theoretical limit for energy consumption: {{math|''[[kT (energy)|kT]]'' ln 2}} consumed per irreversible state change, where ''k'' is the [[Boltzmann constant]] and ''T'' is the operating temperature of the computer.<ref>{{cite journal|title=The physics of forgetting: Landauer's erasure principle and information theory|journal=Contemporary Physics|volume=42|issue=1|doi=10.1080/00107510010018916|pages=25–60|issn=0010-7514|eissn=1366-5812|last1=Vitelli|first1=M.B.|last2=Plenio|first2=V.|date=2001|url=http://www3.imperial.ac.uk/pls/portallive/docs/1/55905.PDF|arxiv=quant-ph/0103108|bibcode=2001ConPh..42...25P|hdl=10044/1/435|s2cid=9092795}}</ref>  [[Reversible computing]] is not subject to this lower bound.  ''T'' cannot, even in theory, be made lower than 3 [[kelvins]], the approximate temperature of the [[cosmic microwave background radiation]], without spending more energy on cooling than is saved in computation. However, on a timescale of 10<sup>9</sup> – 10<sup>10</sup> years, the cosmic microwave background radiation will be decreasing exponentially, which has been argued to eventually enable 10<sup>30</sup> as much computations per unit of energy.<ref>{{cite arXiv|last1=Sandberg|first1=Anders|last2=Armstrong|first2=Stuart|last3=Cirkovic|first3=Milan M.|date=2017-04-27|title=That is not dead which can eternal lie: the aestivation hypothesis for resolving Fermi's paradox|class=physics.pop-ph|eprint=1705.03394}}</ref>  Important parts{{What|date=June 2022}} of this argument have been disputed.<ref>{{cite journal|first1=Charles H.|last1=Bennett|first2=Robin|last2=Hanson|first3=C. Jess|last3=Riedel|title=Comment on 'The Aestivation Hypothesis for Resolving Fermi's Paradox'|url=https://doi.org/10.1007/s10701-019-00289-5|journal=Foundations of Physics|date=1 August 2019|issn=1572-9516|pages=820–829|volume=49|issue=8|doi=10.1007/s10701-019-00289-5|arxiv=1902.06730|bibcode=2019FoPh...49..820B|s2cid=119045181}}</ref>

==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 [[nucleon]]s on the surface of [[neutron star]]s could form complex "molecules",<ref>{{cite encyclopedia |title=Life on neutron stars |encyclopedia=The Internet Encyclopedia of Science |url=http://www.daviddarling.info/encyclopedia/N/neutronstarlife.html }}</ref> which some have suggested might be used for computing purposes,<ref>{{cite web|url=http://www.cs.usu.edu/~degaris/essays/femtotech.html |title=Femtotech? (Sub)Nuclear Scale Engineering and Computation |access-date=October 30, 2006 |url-status=dead |archive-url=https://web.archive.org/web/20041025030505/http://www.cs.usu.edu/~degaris/essays/femtotech.html |archive-date=October 25, 2004 }}</ref> 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 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]]. [[Seth Lloyd]] calculated<ref>{{Cite journal |arxiv = quant-ph/9908043|bibcode = 2000Natur.406.1047L|title = Ultimate physical limits to computation|journal = Nature|volume = 406|issue = 6799|pages = 1047–1054|last1 = Lloyd|first1 = Seth|year = 2000|doi = 10.1038/35023282|pmid = 10984064|s2cid = 75923}}</ref> the computational abilities of an "ultimate laptop" formed by compressing a kilogram of matter into a black hole of radius 1.485 &times; 10<sup>−27</sup> meters, concluding that it would only last about 10<sup>−19</sup> seconds before [[Hawking radiation#Black hole evaporation|evaporating]] due to [[Hawking radiation]], but that during this brief time it could compute at a rate of about 5 &times; 10<sup>50</sup> operations per second, ultimately performing about 10<sup>32</sup> operations on 10<sup>16</sup> bits (~1 [[petabyte|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."<ref>{{cite journal|last=Lloyd |first=Seth |year=2000 |title=Ultimate physical limits to computation |journal=[[Nature (journal)|Nature]] |volume=406 |issue=6799 |pages=1047–1054 |doi=10.1038/35023282 |url=http://puhep1.princeton.edu/~mcdonald/examples/QM/lloyd_nature_406_1047_00.pdf |pmid=10984064 |arxiv=quant-ph/9908043 |url-status=dead |archive-url=https://web.archive.org/web/20080807173904/http://puhep1.princeton.edu/~mcdonald/examples/QM/lloyd_nature_406_1047_00.pdf |archive-date=August 7, 2008 |bibcode=2000Natur.406.1047L |s2cid=75923 }}</ref>
* In ''[[The Singularity Is Near]]'', Ray Kurzweil cites the calculations of Seth Lloyd that a universal-scale computer is capable of 10<sup>90</sup> operations per second. The mass of the universe can be estimated at 3 × 10<sup>52</sup> kilograms. If all matter in the universe was turned into a black hole, it would have a lifetime of 2.8 × 10<sup>139</sup> seconds before evaporating due to Hawking radiation. During that lifetime such a universal-scale black hole computer would perform 2.8 × 10<sup>229</sup> operations.<ref>{{Cite book|title=The Singularity is Near|last=Kurzweil|first=Ray|publisher=New York: Viking|year=2005|pages=911}}</ref>

==Abstract limits in computer science==
In the field of [[theoretical computer science]] the [[Computability theory|computability]] and [[Computational complexity theory|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 <math>\Sigma^0_0=\Pi^0_0=\Delta^0_0</math> 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 function|uncomputable]] functions.

===Loose and tight limits===
Many limits derived in terms of physical constants and abstract models of computation in computer science are loose.<ref>{{cite journal |last=Markov |first=Igor |year=2014 |title=Limits on Fundamental Limits to Computation|journal=[[Nature (journal)|Nature]] |volume=512 |issue= 7513|pages=147–154|doi=10.1038/nature13570 |pmid=25119233 |arxiv=1408.3821 |bibcode=2014Natur.512..147M|s2cid=4458968 }}</ref> Very few known limits directly obstruct leading-edge technologies, but many engineering obstacles currently cannot be explained by closed-form limits.

==See also==
{{div col}}
*[[Digital physics]]
*[[Hypercomputation]]
*[[Matrioshka brain]]
*[[Physics of computation]]
*[[Programmable matter]]
*[[Quantum computing]]
*[[Supertask]]
*[[Transcomputational problem]]
{{div col end}}

==References==
{{Reflist}}

[[Category:Limits of computation| ]]
[[Category:Theory of computation]]