computability theory Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since ex ...

, the theory of real computation deals with hypothetical computing machines using infinite-precision

real number In mathematics, a real number is a number that can be used to measure a continuous one- dimensional quantity such as a duration or temperature. Here, ''continuous'' means that pairs of values can have arbitrarily small differences. Every re ...

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 The Mandelbrot set () is a two-dimensional set (mathematics), set that is defined in the complex plane as the complex numbers c for which the function f_c(z)=z^2+c does not Stability theory, diverge to infinity when Iteration, iterated starting ...

is only partially decidable." These hypothetical computing machines can be viewed as idealised

analog computer An analog computer or analogue computer is a type of computation machine (computer) that uses physical phenomena such as Electrical network, electrical, Mechanics, mechanical, or Hydraulics, hydraulic quantities behaving according to the math ...

s which operate on real numbers, whereas

digital computer A computer is a machine that can be programmed to automatically carry out sequences of arithmetic or logical operations (''computation''). Modern digital electronic computers can perform generic sets of operations known as ''programs'', wh ...

s are limited to

computable number In mathematics, computable numbers are the real numbers that can be computed to within any desired precision by a finite, terminating algorithm. They are also known as the recursive numbers, effective numbers, computable reals, or recursive reals ...

s. They may be further subdivided into differential and

algebra Algebra is a branch of mathematics that deals with abstract systems, known as algebraic structures, and the manipulation of expressions within those systems. It is a generalization of arithmetic that introduces variables and algebraic ope ...

ic models (digital computers, in this context, should be thought of as

topological Topology (from the Greek words , and ) is the branch of mathematics concerned with the properties of a geometric object that are preserved under continuous deformations, such as stretching, twisting, crumpling, and bending; that is, wit ...

, 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 In machine learning, a neural network (also artificial neural network or neural net, abbreviated ANN or NN) is a computational model inspired by the structure and functions of biological neural networks. A neural network consists of connected ...

can have noncomputable real weights, making them able to compute nonrecursive languages.) or vice versa. (

Claude Shannon Claude Elwood Shannon (April 30, 1916 – February 24, 2001) was an American mathematician, electrical engineer, computer scientist, cryptographer and inventor known as the "father of information theory" and the man who laid the foundations of th ...

'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 In computation theory, the Blum–Shub–Smale machine, or BSS machine, is a model of computation introduced by Lenore Blum, Michael Shub and Stephen Smale, intended to describe computations over the real numbers. Essentially, a BSS machine is a Ra ...

(BSS). If real computation were physically realizable, one could use it to solve

NP-complete In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...

problems, and even #P-complete problems, in

polynomial time In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...

. Unlimited precision real numbers in the physical universe are prohibited by the

holographic principle The holographic principle is a property of string theories and a supposed property of quantum gravity that states that the description of a volume of space can be thought of as encoded on a lower-dimensional boundary to the region – such as a ...

and the

Bekenstein bound In physics, the Bekenstein bound (named after Jacob Bekenstein) is an upper limit on the thermodynamic entropy ''S'', or Shannon entropy ''H'', that can be contained within a given finite region of space which has a finite amount of energy—or co ...

Scott Aaronson Scott Joel Aaronson (born May 21, 1981) is an American Theoretical computer science, theoretical computer scientist and Schlumberger Centennial Chair of Computer Science at the University of Texas at Austin. His primary areas of research are ...

,
NP-complete Problems and Physical Reality
', ACM

SIGACT ACM SIGACT or SIGACT is the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory, whose purpose is support of research in theoretical computer science. It was founded in 1968 by Patrick C. Fischer. Publi ...

News, Vol. 36, No. 1. (March 2005), pp. 30–52.

See also

References

Further reading