Iteration, Inequalities, and Differentiability in Analog Computers

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

Journal of Complexity 16 (2000) 642-660.

Shannon's General Purpose Analog Computer (GPAC) is an elegant model of analog computation in continuous time. In this paper, we consider whether the set G of GPAC-computable functions is closed under iteration, that is, whether for any function f(x) in G there is a function F(x,t) in G such that F(x,t) = f^t(x) for non-negative integers t. We show that G is not closed under iteration, but a simple extension of it is. In particular, if we relax the definition of the GPAC slightly to include unique solutions to boundary value problems, or equivalently if we allow functions x^k T(x) that sense inequalities in a differentiable way, the resulting class, which we call G+T_k, is closed under iteration. Furthermore, G+T_k includes all primitive recursive functions, and has the additional closure property that if T(x) is in G+T_k, then any function of x computable by a Turing machine in T(x) time is also.

Click here to download

Cris Moore <>