Computing with Infinite Data: Bridging the Gap between Abstract and Concrete Models

Title: Computing with Infinite Data: Bridging the Gap between Abstract and Concrete Models

Abstract: This research aims to develop a comprehensive theory for specifying, computing, and reasoning with infinite data, such as real numbers, functions, and bit streams. The study focuses on topological many-sorted algebras, which are used to model data types containing infinite data. The main research question is how to compare and integrate high-level, representation-independent abstract models of computation with low-level, representation-dependent concrete models of computation.

Methodology: The study investigates two types of models: abstract and concrete. Abstract models are invariant under isomorphisms and do not depend on any representation. Examples include the 'while' programming language and the BCSS model. Concrete models depend on the choice of representation and are not invariant under isomorphisms. Examples include effective metric spaces and domain representations.

The paper first shows that computing functions on topological algebras using an abstract model requires partial operations and computable functions that are continuous and multivalued. This multivaluedness is necessary even for single-valued functions, so abstract models must be nondeterministic. The 'while'-array programming language with nondeterministic assignment of "countable choice" (WhileCC∗ model) is introduced as an abstract model.

The paper then focuses on metric algebras with effective representations. Among various results, it is proven that any function computable in the effective representation of a metric algebra is also WhileCC∗ approximable. Conversely, under certain conditions, any effective function is also WhileCC∗ approximable. An equivalence theorem and examples of algebras where equivalence holds are provided.

Results: The main result is the development of a unified and stable theory of computation for topological algebras. The paper shows how to compare and integrate abstract and concrete models, providing equivalence theorems and examples.

Implications: The study has significant implications for computer science and related fields. It offers a comprehensive theory for dealing with infinite data, which is crucial for scientific modelling, embedded systems, graphics, and multimedia communications. The unified theory of computation for topological algebras provides a solid foundation for further research and applications.

Link to Article: https://arxiv.org/abs/0108007v1 Authors: arXiv ID: 0108007v1