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?
Asked By : Matthew Matic
Answered By : Mohammad Al-Turkistany
Unfortunately, there is no "universal" concept of universality in analogue computing. However, this paper by Delvenne proposes a unifying formalism for universality in discrete (e.g. Turing Machines) and continuous (e.g. differential equations) dynamical systems and reviews some universal systems studied in the literature. Here is an excerpt from the paper which informally describes the procedure for proving universality of a dynamical system:
But most dynamical systems studied in mathematics and physics have an un-countable state space, e.g., cellular automata, differential equations, piecewise linear maps, etc. Examples of those systems have been proved universal. Their halting problem is imitated from the Turing machine in the following way. We choose a particular countable family of initial states, and countable family of final states, or final sets of states. Then the halting problem is given an initial state and a final state/set of states, whether the trajectory starting from the initial state will reach the final state/set of states. More specific examples are given in Section 7.
Jean-Charles Delvenne, What is a universal computing machine?, Applied Mathematics and Computation, Volume 215, Issue 4, 15 October 2009, Pages 1368-1374
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/1292
0 comments:
Post a Comment
Let us know your responses and feedback