COMPUTATION ON TOPOLOGICAL DATA TYPES

Jeff Zucker
McMaster

Functions on data such as real numbers and discrete or
continuous data streams are fundamental for many kinds of
computation.  Such data types are modelled using topological,
or metric, many-sorted algebras and continuous mappings.

We compare concrete and abstract models of computation on
such data types.  In concrete models, the computations depend
on the representations of the data, e.g. the representation
of (computable) reals by fast Cauchy sequences of rationals.
Abstract models use high level programming languages on the
data, which are given primitively.  In order to derive an
equivalence result between these two classes of models, we
have to consider issues of multivaluedness, continuity and
approximable computability.

This is joint work with John Tucker (Swansea).