J V Tucker: Research
Computation
on Topological Data Types
In recent years my main research interest has been focussed upon problems
concerned with continuous data like real numbers. I will sketch some of
the background and results of recent research.
1. Discrete versus Continuous
Data = Digital versus Analogue Processing
2. What is a topological data type?
3. Concrete computability: Computing via representations
4. Abstract computability: Computing
independently of representations
1. Discrete versus Continuous
Data = Digital versus Analogue Processing
The data used in computing and communication are either discrete
or continuous. Traditionally, the two forms of processing data is called
digital and analogue computation and communication.
Digital computation and communication can be defined to be information
processing with discrete data types.
In a discrete data type, each datum has a finite representation, and
the set of all data can be enumerated, being either finite or countably
infinite.
Examples of discrete data are: Booleans, bits, natural numbers, integers,
rationals, strings, texts, terms, trees, algebraic and logical formulae,
files etc. Indeed, depending on one’s level of abstraction, bits, naturals
and strings are often used to make the necessary finite representations.
Similarly, analogue computation and communication can be defined to
be processing with continuous data types.
In a continuous data type, some datum has only an infinite representation
and the set of all data cannot be enumerated, being uncountably infinite.
Examples of continuous data are: infinite sequences or timed streams
of data such as booleans, bits, natural numbers, integers, rationals, real
numbers; waveforms and signals; infinite sets and functions on infinite
sets, infinite terms and trees etc.
In many systems both discrete and continuous data, and digital and
analogue processing, are essential. The interface between discrete and
continuous data is extremely important in theory and practice. For example,
in Scientific Computation, and in Graphics and Visualisation, passing
from one form of data to the other is termed either the discrete approximation
of continuous data or the interpolation of continuous data from
discrete data.
In Electronics, Communications and Control, the interface is termed
analogue-digital conversion or digital-analogue conversion.
The old debate among digital and analogue computers was largely focussed
on practical comparisons between them as computational tools. It
was ultimately reduced to an competition for versatility, speed, size,
and cost and was won comprehensively by digital computers. The digital
world is still invading the analogue world, of course. Currently and most
notably, it is capturing the design, processing and communication of audio
and visual media.
However, the digital and analogue worlds must coexist and are equally
important in theory and practice. Conceptually, discrete data is insufficient
to model even the simplest parts of the world. For example, the need for
the data type of real numbers, to represent lengths like √2 when measuring
triangles, was known in the mathematics of Classical Greece. For a fine introduction
see T E Rihll Greek Science, Oxford UP, 1999 and her on-line history
Greek
and Roman Science and Technology
We are again finding exciting foundational problems to do with data and
computation because of the need to understand new forms of data, their
representation, and the intimate details of the nature of computations
on both discrete and continuous data, and of the nature of the interfaces
between them. Since 1936, a comprehensive theory of computation on discrete
data has been worked out. In recent years the need for a similarly comprehensive
theory of continuous data has become an urgent challenge.
2. What is a topological
data type?
Since digital computation works with discrete data, digital computations
with continuous data must be computations that are approximate. The problem
is to understand and control the approximations. Approximations
on continuous data can be modelled by topologies on data and by functions
that preserve approximations and which are called continuous functions.
These topologies are often derived from other structures modelling approximations
such as orderings on data and metrics on data.
In general, data types are modelled by many sorted algebras
i.e. sets of data, operations on the data, with tests on data modelled
by Boolean valued functions. Continuous data types are modelled by many
sorted topological algebras. A topological algebra has a topology on
its sets of data with respect to which the operations are continuous. Topological
algebras are virtually everywhere in science and engineering.
In recent years the field of Computable Analysis has blossomed. This
is the study of algorithms that operate on the data type of computable
real numbers, and its generalisations to function spaces. Roughly, it has
two aims:
- To investigate the computability and complexity in the field
of Mathematical Analysis and in its Applications.
- To enable reliable and efficient exact computation with
real numbers, function spaces and other topological spaces.
The theoretical aim has many applications in computing, and is needed
to gain insight when exploring the computability of the physical world.
The practical aim would dramatically improve many areas of Scientific Computation,
where high precision is needed, and the design and validation of safety
critical systems involving real number.
The field of Computable Analysis is very active. The main e-grouping
is called Computability
and Complexity in Analysis (CCA) which runs news groups and conferences
in the subject (e.g., Swansea was host to the Fourth Computability and
Complexity in Analysis 2000, 14-17 September, 2000).
There many approaches to the theory computable functions on topological
spaces and algebras. They can be divided into Concrete Computability
Theories and Abstract Computability Theories, which
I will now introduce to sketch my current research. A comparative study of
the two concepts is the paper with Jeff Zucker (here).
3. Concrete computability – Computing
via representations of topological algebras
In a concrete computability theory the computations are dependent
on some representation of the data. Computations are not uniform, and different
representations can yield different results. Computations are not isomorphism
invariants. Models of computation that are based on concrete ideas
of coding, numbering, or representing data using numbers
or functions are typical of concrete models.
Viggo Stoltenberg-Hansen and I developed a general method of domain
representations of topological algebras in the early 1980s. We had worked
on computability problems for rings and fields, and for arbitrary data
types, in the case they were countable and discrete. We were interested
in the computability of some uncountable structures containing infinite
data, namely:
(i) infinite process algebras;
(ii) complete local rings;
(iii) real number field.
The problem was to find a completely general approach to analysing
what aspects of them were computable. We immediately realised that
there was a common structure to (i) and (ii). They were certain types
of inverse limits and, hence, ultrametric algebras. Note that the equivalence
of ultrametric algebras, domains and inverse limits partially answered
certain questions at the time about the equivalence of certain approaches
to developing process theory.
We developed (a) a general method based on the notion of a topological
universal algebra being represented by maximal elements in a structure
domain and (b) a simple method of representing ultrametric algebras using
domains – specifically algebraic domains. A widely circulated report in
1985, later published in the JSL, presented this theory and applied it
to complete local rings. Later we examined the use of domain representations
in equation solving in ultrametric algebras and its applications to
(i) process algebras and
(ii) infinite synchronous algorithms.
Klaus Weihrauch published an attempt to use cpos to organise representations
of topological spaces. He abandoned this method in favour of the
coding methods based on Baire and Cantor space of his TTE approach.
The domain technique received a tremendous boost in the 1990s when Abbas
Edalat, starting in 1995, used continuous domains to represent spaces and
applied by the work to a wide range of examples, including integration,
iterated maps, differentiable functions and solid geometry - see, e.g.,
his survey in the BSL and his many publications.
Jens Blanck wrote an excellent thesis for Viggo which, among a number
of things, gave the theory for domain representaions of metric spaces, which
opened the door to rountine applications in Analysis. Among the subjects
I have studied with Viggo and Jens are:
Classification of Concrete Models
Until quite recently, the study of computability on topological spaces
consisted of very different disparate and rival approaches, only some which
semmed likely to be equivalent. In a paper we gave proofs of equivalences
between 5 disparate concrete models of computation. This demonstrated that
computation on certain common classes of topological algebras is invariant
under concrete representation techniques and hence is likely to have a stable
theory.
Analogue and Digital Stream Processing
As part of a long standing interest in the foundations of hardware
design, we used our domain representability methods to develop a first
(?) unified theory of continuous time and discrete time streams, their transduction
and conversion.
Volume Graphics
A spatial object is a partial map from space to data. Data types of
spatial objects are modelled by topological algebras of partial maps and
are the foundation for a high level approach to volume graphics called constructive
volume geometry (CVG), where space and data are subspaces of n dimensional
Euclidean space. We investigate the computability of spatial object data
types, in general and in volume graphics, using the theory of effective
domain representations for topological algebras. The basic mathematical
problem considered is to classify which partial functions between topological
spaces can be represented by total continuous functions between given domain
representations of the spaces. We prove theorems about partial functions
on regular Hausdorff spaces and their domain representations, and apply
the results to spatial objects and CVG algebras.
Computable and Continuous Homomorphisms on Metric Partial Algebras
All sorts of algebraic and computational ideas, from linear maps between
Banach algebras to recursion equations and definitions by structural induction,
can be generalised by the study of homomorphisms between metric partial algebras.
Viggo Stoltenberg-Hansen and I have made a thorough analysis of the computability
and continuity of homomorphisms between such algebras. One application is
a generalisation of the Pour El Richards Theorem on computable operators
on Banach spaces.
4. Abstract computability –
Computing independently of representations
In an abstract computability theory the computations are independent
of all the representations of the data. Computations are uniform over all
representations and are isomorphism invariants. Models of computation that
are based on abstract ideas of program, equation, scheme,
or logical formula are typical of abstract models.
For many years, Jeff Zucker and I have been developing the theory of
computability for many sorted algebras. We have created a fairly comprehensive
theory for arbitrary many sorted algebras, and undertaken a large classification
of the different models that have emerged over the past 50 years. A full
introduction to and survey of our work is in our Handbook chapter.
In recent years we have focussed our attention on the problem of developing
the theory specific to topological algebras (especially real number structures
and function spaces) and their many applications. A very special case
of our general theory is the Blum-Shub-Smale theory of real number computation:
see
Here are some of the subjects I have studied.
Approximating with while programs
We studied the role of total and partial functions when computing with
while programs on topological algebras. Some results show that partial
operation and functions play a fundamental role in the theory of computability
in the topological case. Using approximations by while programs
on metric algebras we showed that concrete computability models and approximate
abstract computability models for functions on the real numbers are equivalent.
This is a simple but important bridge built between the theories of concrete
and abstract models. A consequence is that we can now link all concrete
models with an adapted and extended Blum-Shub-Smale theory.
Algebraic specifications of approximately computable functions
We have studied in considerable detail the connection between abstract
computability and algebraic specifications. Among many theorems we have
shown that universal algebraic specifications exist that uniquely define
all approximable abstractly computable functions on metric algebras. We
have applied this to the real numbers in various ways. Thus, we have proved
that: There exists a single finite set of algebraic fromulae whose solutions
are all and only the computably approximable functions on the real numbers.
Nondeterministic computations on topological algebras
We have investigated the equivalence between approximate while
computability and classical computability on the real numbers in more general
settings. We have considered metric partial algebras and compared effective
metric space methods (after Moschovakis) and approximations by while
programs. We found that the while computation is not capable of approximating
many functions on interest – functions that can be computed by concrete
models. We have shown that when the while programming language is
augmented by nondeterministic choice constructs then effective metric
space notions and approximate nondeterministc while computations
are equivalent over a certain large classes of metric partial algebras. This
implies that, with the help of multivalued functions, there
is a general equivalence possible between concrete computation and approximate
abstract computation.