Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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
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).
TL;DR: If by “analogue computers”, you mean differential analysers, the answer is adders, constant units and integrator. Bournez, Campagnolo, Graça and Hainry have shown in 2006 (paywalled / free reprint) that an idealized model of it allows to compute all the computable functions in the framework of computable analysis, and this model only needs these 3 kind of units.
The set of operation you propose (addition, multiplication, subtraction, and division), even completed by root equation is by definition not sufficient to compute any transcendental function. Transcendental functions includes very common functions, like $\sin$, $\exp$, $\log$. However, as discussed below, some analogue computer model allow to compute transcendental functions and, basically all real functions computable by a Turing machine.
As stressed by others, the concept of “universal computation” is less clear for analogue computers than for standard computer, where different natural notion of computability in different computing models where found equivalent in the 1930’s (see Wikipedia page on Church Turing Thesis for details).
In order to define such a universality, one should first define a good model for analogue computation, and it is a difficult task, since the model should be idealized and and natural enough to be useful, but its idealization should not give unrealistic power to the model. An example of such a good idealization is the infinite tape of Turing machines. The problem with analogue computers comes with real numbers which could allow to build unreasonable stuff like the Zeno machine. However, several such models have been proposed and used in the literature (The GPAC is the main subject of this answer, but I try to be complete in the list below, without any hypercomputer):
In his 1941 paper, Shanon introduced the GPAC to model differential analysers.This model only needs 3 kinds of interconnected units (constant units, adders and integrators. Multipliers can be built from integrators and adders.) He showed that the set of functions which it generates is the set of algebraic differential functions, but excludes the hypertranscendental functions. It means that the $\Gamma$ and $\zeta$, which are Turing-computable cannot be generated. In other words, no differential analyser will ever have an output $y(t)=\Gamma(t)$, ant it seemed for a long time that such an analogue computer is not “universal”, since it cannot generate some reasonable computable functions, used by mathematicians.
However, in 2004, Daniel Silva Graça showed that the previous model, based on instantaneous computation is too restrictive. If one define the computability of a function $f$ differently, allowing $y(t)$ to converge towards $f(x)$, for an input $x$, then the $\gamma$ and $\zeta$ functions are computable by a GPAC. Bournez, Campagnolo, Graça and Hainry then showed in 2006 (paywalled / free reprint) that an idealized model of it allows to compute all the computable functions in the framework of computable analysis.
Bournez, Graça and Pouly then showed in 2013 that these analogue computers can efficiently simulate a Turing machine (p.181 of a big pdf) and, in 2014, that the P and NP complexity classes are equivalent in this model.
Would it be useful to propose that a universal analog system could be modelled by an infinite neural net i.e. Any other analog system input/output values can be replicated matched neural network for a given operation, and operations can be chained as required?
While I did formulate this thought on my own, a subsequent search has shown a similar proposal:
What emerges is a Church-Turing-like thesis, applied to the field of analog computation, which features the neural network model in place of the digital Turing machine (see here).
Arguably then all you would need is the primitive operations to move value from one node to another. Off the cuff that could be plus, minus and divide to get ratio between connections.
Now as to the intractable problems, do look at where neural networks have been successfully applied, or are under performing due to being implemented on a a discrete computer.
(and apologies if my nearly lay person view on this topic is glaringly obvious)
