Analog Computability with Differential Equations

Abstract

In this dissertation we study a pioneering model of analog computation called General Purpose Analog Computer (GPAC), introduced by Shannon in 1941. The GPAC is capable of manipulating real-valued data streams. Its power is characterized by the class of differentially algebraic functions, which includes the solutions of initial value problems for ordinary differential equations. We address two limitations of this model. The first is its fundamental inability to reason about functions of more than one independent variable (the `time' variable). In particular, the Shannon GPAC cannot be used to specify solutions of partial differential equations. The second concerns the notion of approximability, a desirable property in computation over continuous spaces that is however absent in the GPAC. To overcome these limitations, we extend the class of data types by taking channels carrying information on a general complete metric space X; for example the class of continuous functions of one real variable. We consider the original modules in Shannon's construction (constants, adders, multipliers, integrators) and add two new modules: a differential module which computes spatial derivatives; and a continuous limit module which computes limits. We then build networks using X-stream channels and the abovementioned modules. This leads us to a framework in which the speci cations of such analog systems are given by fi xed points of certain operators on continuous data streams, as considered by Tucker and Zucker. We study the properties of these analog systems and their associated operators. We present a characterization which generalizes Shannon's results. We show that some non-differentially algebraic functions such as the gamma function are generable by our model. Finally, we attempt to relate our model of computation to the notion of tracking computability as studied by Tucker and Zucker.