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 e ...

, 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 distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...

s. They are given this name because they operate on the set of

s. Within this theory, it is possible to prove interesting statements such as "The complement of the

Mandelbrot set The Mandelbrot set () is the set of complex numbers c for which the function f_c(z)=z^2+c does not diverge to infinity when iterated from z=0, i.e., for which the sequence f_c(0), f_c(f_c(0)), etc., remains bounded in absolute value. This ...

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 computer that uses the continuous variation aspect of physical phenomena such as electrical, mechanical, or hydraulic quantities (''analog signals'') to model the problem being solved. In c ...

s which operate on real numbers, whereas

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

s are limited to

computable numbers 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 or the computable reals or recursive r ...

. They may be further subdivided into differential and

algebra Algebra () is one of the broad areas of mathematics. Roughly speaking, algebra is the study of mathematical symbols and the rules for manipulating these symbols in formulas; it is a unifying thread of almost all of mathematics. Elementary a ...

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

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

, at least insofar as their operation on

computable real 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 or the computable reals or recursive ...

s 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 is a professor of computer science. Her academic position is in the school of Computer Science and the Program of Neuroscience and Behavior at the University of Massachusetts Amherst; she is the director of the school's Biologica ...

neural nets Artificial neural networks (ANNs), usually simply called neural networks (NNs) or neural nets, are computing systems inspired by the biological neural networks that constitute animal brains. An ANN is based on a collection of connected units ...

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 people, American mathematician, electrical engineering, electrical engineer, and cryptography, cryptographer known as a "father of information theory". As a 21-year-o ...

'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

'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, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...

problems, and even #P-complete problems, in

polynomial time In 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 performed by ...

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

holographic principle The holographic principle is an axiom in 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 scientist and David J. Bruton Jr. Centennial Professor of Computer Science at the University of Texas at Austin. His primary areas of research are quantum computing an ...

,
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