Computation by ‘While’ programs on topological partial algebras

AbstractThe 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 program approximable on a simple algebra based on R