An Analog Characterization of the Subrecursive Functions
Manuel L. Campagnolo, Cristopher Moore, José Félix Costa · 2000
. We study a restricted version of Shannon's General Purpose Analog Computer in which we only allow the machine to solve linear dierential 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 dierentiable 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 innity, then it can compute functions on any given level of the Grzegorczyk hierarchy. More precisely, we show that the model contains exactly the nth level of the Grzegorczyk hierarchy if it is allowed to solve n 3 non-linear dierential 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...