Iteration, Inequalities, and Differentiability in Analog Computers

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) 2 G there is a function F(x; t) 2 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 f(x) that sense inequalities in a differentiable way, the resulting class, which we call G + fk, is closed under iteration. Furthermore, G + k includes all primitive recursive functions, and has the additional closure property that if T(x) is in G +k, then any function of x computable by a Turing machine in T(x) time is also.