Editing Real computation

{{short description|Concept in computability theory}}
[[File:Operational amplifier integrator.svg|thumb|[[Circuit diagram]] of an [[analog computing]] element to [[integral|integrate]] a given function. Real computation theory investigates properties of such devices under the [[Platonic ideal|ideal]]izing assumption of infinite precision.]]

In [[computability theory]], the theory of '''real computation''' deals with hypothetical computing machines using infinite-precision [[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]] is only partially decidable."

These hypothetical computing machines can be viewed as idealised [[analog computer]]s which operate on real numbers, whereas [[digital computer]]s are limited to [[computable number]]s. They may be further subdivided into [[differential (mathematics)|differential]] and [[algebra]]ic models (digital computers, in this context, should be thought of as [[topology|topological]], at least insofar as their operation on computable reals is concerned<ref>{{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/}}</ref>). Depending on the model chosen, this may enable real computers to solve problems that are inextricable on digital computers (For example, [[Hava Siegelmann]]'s [[neural nets]] can have noncomputable real weights, making them able to compute nonrecursive languages.) or vice versa. ([[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.)<ref>{{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}}</ref>

A canonical model of computation over the reals is [[Blum–Shub–Smale machine]] (BSS).

If real computation were physically realizable, one could use it to solve [[NP-complete]] problems, and even [[Sharp P|#P]]-complete problems, in [[polynomial time]]. Unlimited precision real numbers in the physical universe are prohibited by the [[holographic principle]] and the [[Bekenstein bound]].<ref>[[Scott Aaronson]], ''[https://arxiv.org/abs/quant-ph/0502072 NP-complete Problems and Physical Reality]'', ACM [[SIGACT]] News, Vol. 36, No. 1. (March 2005), pp. 30–52.</ref>

==See also==
* [[Hypercomputation]], for other such powerful machines.
* [[Real RAM]].
* [[Quantum finite automaton]], for a generalization to arbitrary geometrical spaces.

==References==
<references/>

==Further reading==
*{{cite book|author=[[Lenore Blum]], Felipe Cucker, Michael Shub, and [[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]]
 | 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}}