Alan Turing, Sark, 1931

Basic to recent developments in the subject is the theory of relative computability. This classifies real numbers according to the Turing reducibility relation a < b meaning 'a is computable from knowledge of b', and is captured mathematically via the Turing degree structure. (The structure of the enumeration degrees is the analogous structure derived from nondeterministic Turing reducibility.) Thus if a < b then a is closer to being 'outright computable' than b. Let 0 be the degree of all 'outright computable' reals. Then there is a natural 'jump operation' a' on the degrees which gives rise to a linear scale 0 , 0' , 0'' , .... against which other degrees may be measured. The ordering of the Turing degrees (and also of the enumeration degrees) is a very complex structure, requiring highly sophisticated and technically difficult methods for its analysis. Following the early work of Kleene and Post, its study has formed one of the central areas of research in computability theory over the last fifty years, yet it is only recently that some of the deeper patterns and interrelationships have emerged. For instance, it was only in the period 1989 to 1998 that Kleene and Post's long standing question concerning the Turing definability of the jump was fully solved. Most recently, interest has focused on automorphisms. The nonrigidity of the Turing universe, and its rigidity above 0'' (the latter arising from work of Slaman and Woodin), promise to have far reaching mathematical, scientific and philosophical consequences.

There are still very many open questions, both of a technical nature, concerning extensions of what is known about the Turing degrees and their context in the enumeration degrees, and similar questions for other natural reducibility degree structures, and less well-defined questions concerning the scope of relevance of such work.

A particularly exciting recent development is the renewal of the roots of classical computability in Turing's interest in everyday questions concerning the extent and nature of practical computability. This renewal has many facets, and involves new links between computability theorists, computer scientists, philosophers and theoretical physicists - see for instance the newly formed Computability in Europe network, coordinated from Leeds. CiE held its first international conference - Computability in Europe 2005: New Computational Paradigms in Amsterdam in June, 2005, its second Computability in Europe 2006: Logical Approaches to Computational Barriers in Swansea, and in 2007 Computability in Europe 2007: Computability and Logic in the Real World will be in Siena. At a local level, logicians and computer scientists come together via SIGLaC - the Special Interest Group in Logic and Computation.

Basic information on people working in classical computability can be got from the Computability Theory Home Page. There is also a Computability and Complexity in Analysis network, and one for Foundations of Mathematics, some of whose discussions relate to computability theory. A recent initiative is the Mathematical Logic Forum, a bulletin board for the online discussion of Open Problems in Mathematical Logic. Of historical interest is the Recursive Function Theory Newsletter home page.

Enquiries from prospective research students are always welcome.
See the general information on research possibilities in Pure Mathematics at Leeds University, including details relating to Mathematical Logic.

Logic Colloquium '97 (the 1997 European Meeting of the Association of Symbolic Logic) was held in Leeds, and a substantial part of the programme was devoted to computability theory and related topics.

Members of the Leeds logic group have extensive international links with other researchers, often supported by funding from national and EU sources. For instance, Leeds recently coordinated an INTAS-RFBR Research Project Computability and Models involving researchers from four West European centres (Leeds, Heidelberg, Siena and Turin) and four centres in Russia and Kazakhstan (Ivanovo, Kazan, Novosibirsk and Almaty). Members of the project participated in a workshop in Heidelberg, a number of them going on to the January 2001 Oberwolfach Computability Theory meeting (see above for a photo of the participants - and click on it for a large version).

Current research links include a Chinese NSF Grand International Joint Project New Directions in Theory and Applications of Models of Computation, involving researchers from Leeds, China, New Zealand, Singapore, USA, Russia and Italy.

The first project workshop was held in Beijing, 17-20 May, 2004 (see photo of some of the participants on the left), and the second in May 2005 - see Computation and Logic 2005, Kunming, 17-20 May, 2005

In 2006, the third meeting Theory and Applications of Models of Computation 2006 became a full interdisciplinary international conference, part of a new China-based series of TAMC conferences - see conference photo below. The fourth meeting, TAMC 2007, will be in Shanghai.

Other research interests include complexity theory, graph theory and combinatorics, and applications of logic and computability theory in science and the humanities.
To Barry Cooper's Home Page: