All Topics  
Real computation

 

 
   Email Print
   Bookmark   Link
 

 

Real computation
 
 
  Topics Real computation Topic Home

In computability theory
Computability theory

Computability theory may refer to:* Recursion theory, a branch of mathematical logic, contemporarily called computability theory.* Computability theory , locating basic questions of what is computable within the context of theoretical computer science....
, the theory of real computation deals with hypothetical computing machines using infinite-precision real number
Real number

In mathematics, the real numbers may be described informally in several different ways. The real numbers include both rational numbers, such as 42 and −23/129, and irrational numbers, such as pi and the square root of two; or, a real number can be given by an infinite decimal representation, such as 2.4871773339...., where the digits co...
s. They are given this name because they operate on the set of real number
Real number

In mathematics, the real numbers may be described informally in several different ways. The real numbers include both rational numbers, such as 42 and −23/129, and irrational numbers, such as pi and the square root of two; or, a real number can be given by an infinite decimal representation, such as 2.4871773339...., where the digits co...
s. Within this theory, it is possible to prove interesting statements such as "the complement of the Mandelbrot set
Mandelbrot set

In mathematics, the Mandelbrot set, named after Beno?t Mandelbrot, is a set of Point in the complex plane, the Boundary of which forms a fractal....
 is only partially decidable". For other such powerful machines, see the article Hypercomputation
Hypercomputation

Hypercomputation refers to various hypothetical methods for the computation of non-Computable functions . The term was first introduced in 1999 by Jack Copeland and Diane Proudfoot....
.

These hypothetical computing machines can be viewed as idealised analog computer
Analog computer

An analog computer is a form of computer that uses continuous physical phenomena such as electrical, mechanical, or hydraulic quantities to model the problem being solved....
s which operate on real numbers and are differential
Differential (mathematics)

In mathematics, and more specifically, in differential calculus, the term differential has several interrelated meanings....
, whereas digital computers are limited to computable numbers and are algebraic
Algebraic

Algebraic may refer to:* Algebraic chess notation — a method used to record and describe the play of chess games.* Algebraic data types....
.






Discussion
Ask a question about 'Real computation'
Start a new discussion about 'Real computation'
Answer questions from other users
Full Discussion Forum



Encyclopedia


In computability theory
Computability theory

Computability theory may refer to:* Recursion theory, a branch of mathematical logic, contemporarily called computability theory.* Computability theory , locating basic questions of what is computable within the context of theoretical computer science....
, the theory of real computation deals with hypothetical computing machines using infinite-precision real number
Real number

In mathematics, the real numbers may be described informally in several different ways. The real numbers include both rational numbers, such as 42 and −23/129, and irrational numbers, such as pi and the square root of two; or, a real number can be given by an infinite decimal representation, such as 2.4871773339...., where the digits co...
s. They are given this name because they operate on the set of real number
Real number

In mathematics, the real numbers may be described informally in several different ways. The real numbers include both rational numbers, such as 42 and −23/129, and irrational numbers, such as pi and the square root of two; or, a real number can be given by an infinite decimal representation, such as 2.4871773339...., where the digits co...
s. Within this theory, it is possible to prove interesting statements such as "the complement of the Mandelbrot set
Mandelbrot set

In mathematics, the Mandelbrot set, named after Beno?t Mandelbrot, is a set of Point in the complex plane, the Boundary of which forms a fractal....
 is only partially decidable". For other such powerful machines, see the article Hypercomputation
Hypercomputation

Hypercomputation refers to various hypothetical methods for the computation of non-Computable functions . The term was first introduced in 1999 by Jack Copeland and Diane Proudfoot....
.

These hypothetical computing machines can be viewed as idealised analog computer
Analog computer

An analog computer is a form of computer that uses continuous physical phenomena such as electrical, mechanical, or hydraulic quantities to model the problem being solved....
s which operate on real numbers and are differential
Differential (mathematics)

In mathematics, and more specifically, in differential calculus, the term differential has several interrelated meanings....
, whereas digital computers are limited to computable numbers and are algebraic
Algebraic

Algebraic may refer to:* Algebraic chess notation — a method used to record and describe the play of chess games.* Algebraic data types....
. 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).

A canonical model of computation over the reals is Blum-Shub-Smale machine
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....
 (BSS).

Further reading


  • Lenore Blum
    Lenore Blum

    Lenore Blum received her Ph.D. in mathematics from the Massachusetts Institute of Technology in 1968. She then went to the University of California at Berkeley as a Postdoctoral Fellow and Lecturer in Mathematics....
    , Felipe Cucker, Michael Shub and Stephen Smale
    Stephen Smale

    Stephen Smale is an United States mathematician from Flint, Michigan. He was awarded the Fields Medal in 1966, and spent more than three decades on the mathematics faculty of the University of California, Berkeley ....
    , Complexity and Real Computation, ISBN 0387982817.


External links


  • Neural Networks and Analog Computation: Beyond the Turing Limit by Hava Siegelmann
    Hava Siegelmann

    Hava Siegelmann is a Computer Scientist at the University of Massachusetts who is Director of their Biologically Inspired Neural and Dynamical Systems Lab....
     ISBN 0-8176-3949-7
  • [ftp://ftp.cs.cuhk.hk/pub/neuro/papers/jcss1.ps.Z On the computational power of neural nets]