Manuel Campagnolo, José Costa, Cristopher Moore
Paper #: 00-01-005
We study a restricted version of Shannon's General Purpose Analog Computer in which we only allow the machine to solve linear differential equations. This corresponds to only allowing local feedback in the machine's variables. We show that if this computer is allowed to sense inequalities in a differentiable way, then it can compute exactly the elementary functions. Furthermore, we show that if the machine has access to an oracle which computes a function $f(x)$ with a suitable growth as $x$ goes to infinity, then it can compute functions on any given level of the Grzegorczyk hierarchy. More precisely, we show that the model contains exactly the $n$th level of the Grzegorczyk hierarchy if it is allowed to solve $n-3$ nonlinear differential equations of a certain kind. Therefore, we claim that there is a close connection between analog complexity classes, and the dynamical systems that compute them, and classical sets of subrecursive functions.