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

 
Back to JVT Research
Back to JVT Home Page