An analog characterization of the subrecursive functions

Manuel Lameiras Campagnolo, Cristopher Moore, and Jos'e F'elix Costa

To appear in the proceedings of the 4th Conference on Real Numbers and Computers.

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 Grzegorzyck hierarchy. More precisely, we show that the model contains exactly the n'th level of the Grzegorzyck hierarchy if it is allowed to solve n-3 non-linear differential equations of a certain kind. Therefore, we claim that, at least in this region of the complexity hierarchy, there is a close connection between analog complexity classes, and the dynamical systems that compute them, and classical sets of subrecursive functions.

Click here to download Postscript

Click here to download PDF

Cris Moore <>