3
$\begingroup$

Is there anything that hints at the possibility of a (modern) continuous-value computer, since modern computers are based on discrete arithmetic?

I guess the old analog computers were of this continuous-value type, but is there any modern development?

Do you know something about the issues regarding computability on such machine?

$\endgroup$
  • $\begingroup$ Perhaps you are referring to "analogue" computers? They have major issues with error and have never really been practical. We can do a lot with computable real numbers however (see emab's answer). $\endgroup$ – Jake Jul 28 '15 at 19:35
  • $\begingroup$ There might be something around the corner. E.g. biocomputers. $\endgroup$ – mavavilj Jul 28 '15 at 19:38
  • 3
    $\begingroup$ @Jake I disagree that analogue computers "have never really been practical". Word War II bomb aiming systems, artillery sights and anti-aircraft guns used computers that were exclusively analogue. Sure, they were nothing like as effective as their modern-day equivalents but they were far better than anything else available at the time. $\endgroup$ – David Richerby Jul 28 '15 at 20:40
  • 2
    $\begingroup$ Slightly later on, the SR-71 Blackbird's engine inlet systems were originally controlled by analogue computers, which weren't replaced by digital until the 1980s. As I recall, those and the U-2s also used inertial navigation systems based on analogue computers (but I may have misremembered that part). $\endgroup$ – David Richerby Jul 28 '15 at 20:46
  • $\begingroup$ I was unaware of that bit of history; Thanks! So I stand corrected. Perhaps I should say that general purpose analogue computes were never made to be as practical as today's computers. $\endgroup$ – Jake Jul 28 '15 at 20:46
2
$\begingroup$

Since you asked about computability and computational complexity for computers working on continuous values, you might be interested in research on computational complexity for the reals. In particular, there is a great deal of research on computational complexity for computations that work with real numbers ($\mathbb{R}$).

Normally, we think of algorithms as operating on discrete values (which can be expressed using bits). However, one can also study algorithms that work with real numbers, where the algorithm can use standard operations on real numbers: addition, multiplication, comparison, etc. Imagine that each basic operation on real numbers takes $O(1)$ time. Now we can talk about the running time of algorithms that use these basic operations, and talk about the class of polynomial-time algorithms. We can also look at a computational task, and ask about its complexity: about the running time of the best algorithm for that task. For example, a task might be something like: given a polynomial $p(x)$ with real-valued coefficients, determine whether it has a real root or not.

One can then define an analog of P, namely, $P_\mathbb{R}$ -- the class of problems that have a polynomial-time algorithm, where the algorithm is allowed to do basic operations on real numbers. One can also define an analog of NP, namely, $NP_\mathbb{R}$. This lets one ask interesting questions, like whether $P_\mathbb{R} = NP_\mathbb{R}$. Anyway, there is a rich literature on this, pioneered by Blum, Cucker, Shub, Smale, and others. It is known as complexity and real computation, and sometimes known as the BSS model. If you search the research literature, you'll find lots of work in this area.

The BSS model does have significant limitations. It assumes that all computations on real numbers can be done in $O(1)$ time, to infinite precision, with no error. Real analog computers won't have that property. But it's still a useful and interesting theory, nonetheless.

To learn more, you can look at https://en.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smale_machine and https://cstheory.stackexchange.com/q/2119/5038 and https://cstheory.stackexchange.com/a/2062/5038 and https://cstheory.stackexchange.com/q/31626/5038 and https://cstheory.stackexchange.com/q/27508/5038.

$\endgroup$
1
$\begingroup$

I am considering that by "continues-value" you mean real values.

In terms of computability, there is a field called computable analysis and you might find some useful in these notes: http://eccc.hpi-web.de/resources/pdf/ica.pdf

This field studies the computability of real functions. I suggest you to go through extensions of theorems in computability theorem (all mentioned in the attached link) in order to understand the idea.

$\endgroup$
1
$\begingroup$

It seems that the discovery of memristor have fueled such efforts recently. I have two examples, the paper Boolean Logic Gates From A Single Memristor and a news of a memristor-based computer implementing a basic artificial neural network.

$\endgroup$
0
$\begingroup$

what you refer to is known generally as "analog computation". electronic and mechanical analog computers exist and are widespread but are "specialized". binary computing handles the problem of imprecision/ noise in the computation which tends to be difficult otherwise. here are two possible/ particular angles for "modern research" into analog computing that come to mind, both have much related material & further refs.

an excellent modern reference/ survey on the capabilities/ potentials of analog computing is the following. it is focused on NP complete computation but can be regarded as quite general wrt physical machine models.

another broad area of theoretical and applied investigation is modern implementations of Babbages analytical/ calculating engine which can be generally regarded as a mix of analog and digital elements. a massive working version has finally been built for the first time in centuries by intrepid designer(s) and toured at various museums internationally. see eg

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.