patternMinor
Is there any development in continuous-value computers?
Viewed 0 times
anyvaluecomputersdevelopmenttherecontinuous
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#44805, answer score: 2
Revisions (0)
No revisions yet.