Computation on Streams: Analog and Digital Models
We consider networks of modules connected by channels, processing data from a metric space $A$ (e.g. the reals), and operating with respect to a global continuous clock $\mathbb{T}$, modeled by the set of non-negative reals. The inputs and output of the network are continuous streams, i.e. functions from $\mathbb{T}$ to $A$, forming the stream algebra $\mathcal{C}[\mathbb{T},A]$.
The semantics of the network is obtained from fixed points of contracting functionals over $\mathcal{C}[\mathbb{T},A]$.
In particular, we have investigated analog networks based on Shannon's GPAC ("general purpose analog computer"). It is known that the GPAC computable functions are those solvable by partial differential algebraic equations. It follows that certain well-known functions, such as the gamma function and the Riemann zeta function, are not GPAC computable. This motivates an extension of the GPAC to the L-GPAC model ("L" for limit), which permits the use of limiting operations. This in turn permits the generation of both the gamma function and Riemann zeta function.
It is desirable to compare the power of analog and digital computation models on $\mathcal{C}[\mathbb{T},A]$. We conjecture that the class of L-GPAC-computable functions is equal to the class of functions computable by classical digital models, such as "tracking" and Grzegorczyk-Lacombe computability.
This is joint work with John Tucker, Nick James and Diogo Pocas. Research was funded by a grant from NSERC.