J.V. Tucker and J.I. Zucker (1998):
Computation by `while' programs on topological partial algebras,
McMaster University, Dept of Computer Science, Technical Report 98-02;
to appear in Theoretical Computer Science.
[PDF via ScienceDirect]
Abstract. The language of `while' programs is a fundamental model for imperative programming on any data type. It leads to a generalisation of the theory of computable functions on the natural numbers to the theory of computable functions on any many-sorted algebra.
The language is used to express many algorithms in scientific computing where `while' programs are applied to continuous data. In the theory of data, continuous data types are modelled by topological many-sorted algebras. We study both exact and approximate computations by `while' programs, and `while' programs with arrays, over topological many-sorted algebras with partial operations. First, we establish that partial operations are necessary in order to compute a wide range of continuous functions. We prove basic continuity properties of our abstract computability:
Any partial function computable over a partial topological algebra by a `while'-array program is continuous. Any set semicomputable, or computable, over a partial topological algebra by a `while'-array program is open, or clopen, respectively.
Secondly, we contrast exact and approximate computations. The class of functions that can be computed exactly can be quite limited. We show that on connected total algebras, the `while' and `while'-array computable functions are precisely those that are explicitly definable by terms. We show that for certain general classes of topological algebras, the total functions that can be approximated by `while' programs are precisely those that can be effectively approximated by terms. This property we call generalised Weierstrass approximation. An application of this result is that a function on the set R of reals is computable in the sense of computable analysis if, and only if, it is `while' approximable on a simple algebra based on R.