Digital simulation of analog computation and Church's thesis

Church's thesis, that all reasonable definitions of “computability” are equivalent, is not usually thought of in terms of computability by a continuous computer, of which the general-purpose analog computer (GPAC) is a prototype. Here we prove, under a hypothesis of determinism, that the analytic outputs of a C ∞ GPAC are computable by a digital computer. In POE, Theorems 5, 6, 7, and 8, Pour-El obtained some related results. (The proof there of Theorem 7 depends on her Theorem 2, for which the proof in POE is incorrect, but for which a correct proof is given in LIR. Also, the proof in POE of Theorem 8 depends on the unproved assertion that a solution of an algebraic differential equation must be analytic on an open subset of its domain. However, this assertion was later proved in BRR.) As in POE, we reduce the problem to a problem about solutions of certain systems of algebraic differential equations (ADE's). If such a system is nonsingular (i.e. if the “separant” does not vanish along the given solution), then the argument is very easy (see VSD for an even simpler situation), so that the essential difficulties arise from singular systems. Our main tools in handling these difficulties are drawn from the excellent (and difficult) paper DEL by Denef and Lipshitz. The author especially wants to thank Leonard Lipshitz for his kind help in the preparation of the present paper. We emphasize here that our proof of the simulation result applies only to the GPAC as described below. The GPAC's form a natural subclass of the class of all analog computers, and are based on certain idealized components (“black boxes”), mostly associated with the technology of past decades. One can easily envisage other kinds of black boxes of an input-output character that would lead to different kinds of analog computers. (For example, one could incorporate delays, or spatial integrators in addition to the present temporal integrators, etc.) Whether digital simulation is possible for these “extended” analog computers poses a rich and challenging set of research questions.