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