patternModerate
What is required for universal analogue computation?
Viewed 0 times
whatanaloguecomputationuniversalforrequired
Problem
What operations need to be performed in order to do any arbitrary analogue computation? Would addition, subtraction, multiplication and division be sufficient?
Also, does anyone know exactly what problems are tractable using analogue computation, but not with digital?
Also, does anyone know exactly what problems are tractable using analogue computation, but not with digital?
Solution
I don't think the question can be answered unless we have a definition of what kind of computations we are talking about.
Universality of a machine model w.r.t. a class of computationw means that any computation in that class can be computed by a machine. Unless you define the class of "arbitrary analogue computations", we cannot answer what is universality w.r.t. to them.
Now, the functions you have listed will only give you polynomials and their quotient which is a rather small class of real functions, you cannot even compute simple functions like $2^x$, $\lfloor x \rfloor$, $\sqrt x$, ... using them.
If your question is if there are physical systems that starting from an initial state will reach another state in some time and if that is always computable, then the answer depends on what kind of physics we are talking about, and what it means to set up an initial configuration and observing the result, etc.
If we are just talking mathematically about classical physics (we can set any initial configuration to infinite precision and without any considerations about things like energy needed to set up the configuration and observing the result is similarly from mathematical point of view) then it has been know for long time that there are differential equations about computable functions s.t. their solution is not computable, see Marian B. Pour-El, and J. Ian Richards, "Computability in Analysis and Physics", 1989.
An interesting case is if the n-body problem is computable (and if I remember correctly the answer is no, at least for $n>4$).
Generally, if we can just check equality of two real numbers that gives a function which is not continuous w.r.t. typical typologies of information about real numbers and therefore cannot be computed by a Turing machine since any function (including higher type functions) that a Turing machine can compute is continuous (w.r.t. the topology of information).
Universality of a machine model w.r.t. a class of computationw means that any computation in that class can be computed by a machine. Unless you define the class of "arbitrary analogue computations", we cannot answer what is universality w.r.t. to them.
Now, the functions you have listed will only give you polynomials and their quotient which is a rather small class of real functions, you cannot even compute simple functions like $2^x$, $\lfloor x \rfloor$, $\sqrt x$, ... using them.
If your question is if there are physical systems that starting from an initial state will reach another state in some time and if that is always computable, then the answer depends on what kind of physics we are talking about, and what it means to set up an initial configuration and observing the result, etc.
If we are just talking mathematically about classical physics (we can set any initial configuration to infinite precision and without any considerations about things like energy needed to set up the configuration and observing the result is similarly from mathematical point of view) then it has been know for long time that there are differential equations about computable functions s.t. their solution is not computable, see Marian B. Pour-El, and J. Ian Richards, "Computability in Analysis and Physics", 1989.
An interesting case is if the n-body problem is computable (and if I remember correctly the answer is no, at least for $n>4$).
Generally, if we can just check equality of two real numbers that gives a function which is not continuous w.r.t. typical typologies of information about real numbers and therefore cannot be computed by a Turing machine since any function (including higher type functions) that a Turing machine can compute is continuous (w.r.t. the topology of information).
Context
StackExchange Computer Science Q#1292, answer score: 11
Revisions (0)
No revisions yet.