Computability

• Computing with continuous and analogue data
• Computability and physical systems
• Theory of data and data-centric computing

What can and what can not be computed, now or in the future? Computability theory began with the attempt to answer to this fundamental question in the 1930s. Alan Turing introduced models of machines for computing with discrete symbols, such as 0 and 1, and discovered the existence of universal machines and non-computable problems.

At Swansea we are extending the classical theory of digital computation to all forms of discrete and continuous data. We have created a general theory that captures computability on any data type and are applying it in a variety of areas.

One ambitious aim is to expand the conception of computation to deal with any physically conceived form of data representation and any physical means of computation. Such new computability theories theory might enable us to:

1. unify and integrate analogue and digital computation;
2. suggest new physical technologies for computing;
3. explain hardware/software interfaces;
4. suggest principles for specification, programming and reasoning
   about physical systems;
5. establish physical limits to computation; and, possibly,
6. establish logical limits to our physical knowledge.

Computing with continuous and analogue data

U Berger, J Blanck, J V Tucker

One problem we are attacking is: To unify the computational theories, methods and tools for computing with analogue and digital data. J V Tucker and J I Zucker (McMaster) have developed an extensive and general theory of computable functions on algebras, which model any kind of data. Continuous data types such as the real numbers, waveforms and signals, spectra, infinite data streams, state spaces, function spaces, etc., can be modelled using topological algebras. Our aim is to create a comprehensive computability theory for functions on topological algebras, from which we can derive exact methods for the specification, computation and reasoning with real numbers. Recent discoveries include the surprising theorem that there exists a single “universal” finite set of algebraic formulae, with a number parameter n, that can define uniquely all the computably approximable functions on any metric data type (e.g., the reals, normed spaces, etc.) as n varies.

A second problem is: What are the technological limits of analogue computation? We are working toward a theory of computing with analogue fields. We have created a completely general network model of analogue computing systems distributed in space and operating in continuous time with data from a metric space. The model allows us to analyse analogue computation as an experimental process, develop case studies of mechanical and electrical systems, write equational specifications of analogue networks, and prove theorems about the unique solution and computability of the well-posed analogue networks.

Computability and physical systems

E J Beggs (Maths), J V Tucker

In the search for new physical foundations for computation and information processing, E J Beggs and J V Tucker are developing a theory of functions computable by experiments with physical systems. A fundamental problem is to identify what exactly is an experimental procedure on analogue data, how can it be used to compute, and how does it compare with algorithmic procedures based on digital data. Examples of exotic low dimensional mechanical systems have been created that can compute all functions and all real numbers. Our results lead to an analysis of the construction and observation of physical systems in experiments and the use of new types of programming languages to express experimental procedures.

Theory of data and data-centric computing

J V Tucker

Data is everywhere and data sets are vast. Data is collected in the scientific analysis of the natural world; the functioning of machines and social organizations; the movements of sports people; in the files of the police and secret service, credit agencies and hospitals; in the customer records of the supermarket; in the packets and pages distributed across the internet and the phone networks; in the videos of our streets from cctv cameras and satellites. Data is a commodity. In data-centric computation the primary object of scientific study is data.

At Swansea we research on data and are developing the new paradigm of data-centric computation. Typical questions are: How do you specify and represent data, how you compute and communicate with data, how do you deduce knowledge and information from data? Researchers in visual computing, we also interested in the question: How do you visualize data? Can these diverse types of data, with their distinct applications, be unified conceptually and practically? Surprisingly, data in its digital form can be unified by a general mathematical theory of data based on algebra and logic. It is a theory with profound implications, useful software tools and many applications.