Real computation

Real computation

In computability theory, the theory of real computation deals with hypothetical computing machines using infinite-precision real numbers. 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". For other such powerful machines, see the article Hypercomputation.

These hypothetical computing machines can be viewed as idealised analog computers which operate on real numbers and are differential, whereas digital computers are limited to computable numbers and are algebraic. 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 (BSS).

Further reading

* Lenore Blum, Felipe Cucker, Michael Shub and Stephen Smale, "Complexity and Real Computation", ISBN 0387982817.

External links

* "Neural Networks and Analog Computation: Beyond the Turing Limit" by Hava Siegelmann ISBN 0-8176-3949-7
* [http://www.lsm.tugraz.at/papers/lsm-telematik.pdf the Liquid Computer A Novel Strategy for Real-Time Computing on Time Series, by Thomas Natschläger et al]
* [ftp://ftp.cs.cuhk.hk/pub/neuro/papers/jcss1.ps.Z On the computational power of neural nets]
* [http://math.isa.utl.pt/~mlc/phdthesis.ps Computational complexity of real valued recursive functions and analog circuits. by Campagnolo]


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Computation — is defined as any type of calculation.[1] Also defined as use of computer technology in Information processing.[2][3]Computation is a process following a well defined model understood and expressed in an algorithm, protocol, network topology, etc …   Wikipedia

  • Real number — For the real numbers used in descriptive set theory, see Baire space (set theory). For the computing datatype, see Floating point number. A symbol of the set of real numbers …   Wikipedia

  • Real time Java — is a catch all term for a combination of technologies that allows programmers to write programs that meet the demands of Real time systems in the Java programming language.Java s sophisticated memory management, native support for threading and… …   Wikipedia

  • Real-time computing — In computer science, real time computing (RTC) is the study of hardware and software systems that are subject to a real time constraint i.e., operational deadlines from event to system response. By contrast, a non real time system is one for… …   Wikipedia

  • Computation in the limit — In computability theory, a function is called limit computable if it is the limit of a uniformly computable sequence of functions. The terms computable in the limit and limit recursive are also used. One can think of limit computable functions as …   Wikipedia

  • Real-time locating — Articleissues confusing=July 2008 refimprove=May 2008 essay=May 2008: This page specifically concerns operational aspects of RTLS. For methodology issues see locating engine. For technology issues see wireless. According to ISO/IEC JTC1 SC31 and… …   Wikipedia

  • Real closed field — In mathematics, a real closed field is a field F in which any of the following equivalent conditions are true:#There is a total order on F making it an ordered field such that, in this ordering, every positive element of F is a square in F and… …   Wikipedia

  • real time — /ree euhl, reel/ 1. Computers. the actual time elapsed in the performance of a computation by a computer, the result of the computation being required for the continuation of a physical process. 2. the actual time during which a process takes… …   Universalium

  • Real time factor — The real time factor (RTF) is a common metric of measuring the speed of an automatic speech recognition system. It can also be used in other context where an audio or video signal is processed (usually automatically) at nearly constant rate (e.g …   Wikipedia

  • Computation Tree Logic — Die Computation Tree Logic (kurz CTL) ist eine Temporale Logik, die speziell zur Spezifikation und Verifikation von Computersystemen dient. Meist wird sie auch mit CTL* bezeichnet. CTL bezeichnet dann eine spezielle Teilmenge der CTL* Formeln.… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”