Real computation
Encyclopedia
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 number
s. 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 computers are limited to computable numbers. They may be further subdivided into differential
and algebraic
models (digital computers, in this context, should be thought of as topological
, at least insofar as their operation on computable reals is concerned ). 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).
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 #P-complete problems, in polynomial time, answering affirmatively the P = NP problem. Unlimited precision real numbers in the physical universe are prohibited by the holographic principle
and the Bekenstein bound
.
Computability theory
Computability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability and definability...
, the theory of real computation deals with hypothetical computing machines using infinite-precision real number
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
s. They are given this name because they operate on the set of real number
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
s. Within this theory, it is possible to prove interesting statements such as "the complement of the Mandelbrot set
Mandelbrot set
The Mandelbrot set is a particular mathematical set of points, whose boundary generates a distinctive and easily recognisable two-dimensional fractal shape...
is only partially decidable".
These hypothetical computing machines can be viewed as idealised analog computer
Analog computer
An analog computer is a form of computer that uses the continuously-changeable aspects of physical phenomena such as electrical, mechanical, or hydraulic quantities to model the problem being solved...
s which operate on real numbers, whereas digital computers are limited to computable numbers. They may be further subdivided into differential
Differential (mathematics)
In mathematics, the term differential has several meanings.-Basic notions:* In calculus, the differential represents a change in the linearization of a function....
and algebraic
Algebraic
Algebraic may refer to any subject within the algebra branch of mathematics and related branches like algebraic geometry and algebraic topology.Algebraic may also refer to:...
models (digital computers, in this context, should be thought of as topological
Topology
Topology is a major area of mathematics concerned with properties that are preserved under continuous deformations of objects, such as deformations that involve stretching, but no tearing or gluing...
, at least insofar as their operation on computable reals is concerned ). Depending on the model chosen, this may enable real computers to solve problems that are inextricable on digital computers (for example, Hava Siegelmann
Hava Siegelmann
Hava Siegelmann is a computer scientist at the University of Massachusetts and director of the school's Biologically Inspired Neural and Dynamical Systems Lab. In the early 1990s she proposed a new computational model, the Artificial Recurrent Neural Network , and proved that it could perform...
'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).
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
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
problems, and even #P-complete problems, in polynomial time, answering affirmatively the P = NP problem. Unlimited precision real numbers in the physical universe are prohibited by the holographic principle
Holographic principle
The holographic principle is a property of quantum gravity and string theories which states that the description of a volume of space can be thought of as encoded on a boundary to the region—preferably a light-like boundary like a gravitational horizon...
and the Bekenstein bound
Bekenstein bound
In physics, the Bekenstein bound is an upper limit on the entropy S, or information I, that can be contained within a given finite region of space which has a finite amount of energy—or conversely, the maximum amount of information required to perfectly describe a given physical system down to the...
.