Relative Computability and the Enumeration Degrees

Our survival in the world depends very much on the computable nature of its causal relations. As Einstein put it: "When we say that we understand a group of natural phenomena, we mean that we have found a constructive theory which embraces them". There are various ways of modelling the computable content of causality in the real world, the best known of which is due to the British mathematician, Alan Turing. The notion of Turing reducibility, allowing computation between real numbers using so-called oracles, is sufficient to capture the basics of familiar physical frameworks, such as that of Newtonian dynamics. One can extend the range of contexts to which the model applies by allowing computation via non-deterministic Turing machines. The resulting reducibility - an extension of Turing reducibility - is called enumeration reducibility, and leads to a quite beautiful and richly complex mathematical structure, termed the enumeration degrees. This structure enables us to model computation relative to possibly incomplete information, which is very relevant to a world in which knowledge is developing organically over time, without predictable availability.

Researchers from Leeds have made major contributions to the ongoing project of characterising the structure of the enumeration degrees, and to the understanding of the real-world consequences. Much of the research has concerned the local structure, whereby information which can be approximated accessibly is degree-theoretically classified. There are many open problems, some approachable, others long-standing and full of conceptual and technical challenges. Some of these problems concern the character of the natural embedding of the Turing degrees within the enumeration degrees. Others concern fundamental questions about the describability - that is, definability - of basic information content in the structure. And there is a wide range of questions relating to structural aspects, the understanding of which may supply the key to solving major open problems relating to definability and automorphisms, both at the local and global levels.

Professor S. Barry Cooper is a world leader in this area, and his well-known text on 'Computability Theory' provides an approachable introduction to this and other research topics. He has had a remarkably successful record of supervising research students, a number of which have gone on to do internationally leading work in the field.

The Mathematical Logic Group at Leeds

The Leeds Logic Group is one of the largest and most distinguished of such groups in the world, maintaining a full spectrum expertise across logic as a whole. It maintains a regular Logic Seminar, and a range of specialist research seminars, attracting frequent visitors from the UK and abroad.
Within the Logic Group, the Computability Group is known internationally for its unique contribution to the subject, both scientifically and within the organisational structures responsible for conferences, journals and funding initiatives. Professor Barry Cooper is President of the association Computability in Europe, is on the Editorial Board of the journal 'Computability', and is Chair of the Turing Centenary Advisory Committee.