Research | Logic | Computability | Seminars | PhD students | Conferences | Personal | Teaching | Leeds |
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: