# Real computation
> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Real_computation
> Markdown URL: https://mediated.wiki/source/Real_computation.md
> Source: https://en.wikipedia.org/wiki/Real_computation
> Source revision: 1328232803
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)
{{short description|Concept in computability theory}}
[[File:Operational amplifier integrator.svg|thumb|[Circuit diagram](/source/Circuit_diagram) of an [analog computing](/source/analog_computing) element to [integrate](/source/integral) a given function. Real computation theory investigates properties of such devices under the [ideal](/source/Platonic_ideal)izing assumption of infinite precision.]]
In [computability theory](/source/computability_theory), the theory of '''real computation''' deals with hypothetical computing machines using infinite-precision [real number](/source/real_number)s. They are given this name because they operate on the set of real numbers. Within this theory, it is possible to prove interesting statements such as "The complement of the [Mandelbrot set](/source/Mandelbrot_set) is only partially decidable."
These hypothetical computing machines can be viewed as idealised [analog computer](/source/analog_computer)s which operate on real numbers, whereas [digital computer](/source/digital_computer)s are limited to [computable number](/source/computable_number)s. They may be further subdivided into [differential](/source/differential_(mathematics)) and [algebra](/source/algebra)ic models (digital computers, in this context, should be thought of as [topological](/source/topology), at least insofar as their operation on computable reals is concerned[{{cite book|title=A Simple Introduction to Computable Analysis|author=Klaus Weihrauch|year=1995|url=http://eccc.uni-trier.de/static/books/A_Simple_Introduction_to_Computable_Analysis_Fragments_of_a_Book/}}]). Depending on the model chosen, this may enable real computers to solve problems that are inextricable on digital computers, or vice versa. For example, [Hava Siegelmann](/source/Hava_Siegelmann)'s [neural nets](/source/neural_nets) can have noncomputable real weights, making them able to compute nonrecursive languages. [Claude Shannon](/source/Claude_Shannon)'s idealized analog computer can only solve algebraic differential equations, while a digital computer can solve some transcendental equations as well. However this comparison is not entirely fair since in Claude Shannon's idealized analog computer computations are immediately done; i.e. computation is done in real time. Shannon's model can be adapted to cope with this problem.[{{cite journal|author1=O. Bournez |author2=M. L. Campagnolo |author3=D. S. Graça |author4=E. Hainry |name-list-style=amp |title=Polynomial differential equations compute all real computable functions on computable compact intervals|journal=Journal of Complexity|volume=23|issue=3|pages=317–335|date=Jun 2007|doi=10.1016/j.jco.2006.12.005|doi-access=free|hdl=10400.1/1011|hdl-access=free}}]
A canonical model of computation over the reals is the [Blum–Shub–Smale machine](/source/Blum%E2%80%93Shub%E2%80%93Smale_machine) (BSS).
If real computation were [physically realizable](/source/physically_realizable), one could use it to solve [NP-complete](/source/NP-complete) problems, and even [#P](/source/Sharp_P)-complete problems, in [polynomial time](/source/polynomial_time). Unlimited precision real numbers in the physical universe are prohibited by the [holographic principle](/source/holographic_principle) and the [Bekenstein bound](/source/Bekenstein_bound).[[Scott Aaronson](/source/Scott_Aaronson), ''[https://arxiv.org/abs/quant-ph/0502072 NP-complete Problems and Physical Reality]'', ACM [SIGACT](/source/SIGACT) News, Vol. 36, No. 1. (March 2005), pp. 30–52.]
==See also==
* [Hypercomputation](/source/Hypercomputation), for other such powerful machines.
* [Real RAM](/source/Real_RAM).
* [Quantum finite automaton](/source/Quantum_finite_automaton), for a generalization to arbitrary geometrical spaces.
==References==
==Further reading==
*{{cite book|author=[Lenore Blum](/source/Lenore_Blum), Felipe Cucker, Michael Shub, and [Stephen Smale](/source/Stephen_Smale)|title=Complexity and Real Computation|isbn=0-387-98281-7|year=1998|title-link= Complexity and Real Computation|publisher=Springer }}
*{{cite book|last=Campagnolo|first=Manuel Lameiras|title=Computational complexity of real valued recursive functions and analog circuits|publisher=Universidade Técnica de Lisboa, Instituto Superior Técnico|date=July 2001}}
*{{cite book|author=Natschläger, Thomas, Wolfgang Maass, Henry Markram|title=The "Liquid Computer" A Novel Strategy for Real-Time Computing on Time Series|url=http://www.lsm.tugraz.at/papers/lsm-telematik.pdf}}
*{{cite book|last=Siegelmann|first=Hava|title=Neural Networks and Analog Computation: Beyond the Turing Limit|isbn=0-8176-3949-7|authorlink=Hava Siegelmann|date=December 1998|publisher=Springer }}
*{{cite journal
| last1 = Siegelmann | first1 = Hava T. | author1-link = Hava Siegelmann
| last2 = Sontag | first2 = Eduardo D. | author2-link = Eduardo D. Sontag
| doi = 10.1006/jcss.1995.1013
| issue = 1
| journal = [Journal of Computer and System Sciences](/source/Journal_of_Computer_and_System_Sciences)
| mr = 1322637
| pages = 132–150
| title = On the computational power of neural nets
| url = https://binds.cs.umass.edu/papers/1995_Siegelmann_JComSysSci.pdf
| volume = 50
| year = 1995}}
Category:Models of computation
Category:Hypercomputation
Category:Real numbers
{{Comp-sci-stub}}
---
Adapted from the Wikipedia article [Real computation](https://en.wikipedia.org/wiki/Real_computation) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Real_computation?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.