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

Digital computation and communication can be defined to be information processing with

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

In a continuous data type, some datum has only an

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

In Electronics, Communications and Control, the interface is termed

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

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.

In general, data types are modelled by

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 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

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:

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.

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.

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

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.

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.

We studied the role of total and partial functions when computing with

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:

We have investigated the equivalence between approximate