Much of my research relates to properties of degree structures generated by notions of relative algorithmic strength. Such structures - as exemplified by the Turing degrees - allow us to obtain a classification of countable sets in terms of information content. The basic notion underlying this classification is the question of whether, given two sets of natural numbers A and B, there is an algorithm which, when equipped with the information in B, can compute A, or vice versa. This notion gives rise to equivalence classes of sets, where A and B are in the same equivalence class - called a Turing degree - if both A is computable from B and B is computable from A in the above sense. The Turing degrees form an upper semi-lattice under the induced partial ordering relation between degrees. This is known as the Structure of the Turing Degrees.
My work has involved investigating similar degree structures but where the basic algorithmic notion only uses positive information. In particular much of my work has been focussed on the (so called) Enumeration Degrees and in particular on trying to better understand the first order properties of this structure.
Another main strand of my research concerns computable structures within Mathematics, i.e. structures in which both the domain, as also the relations and functions over the domain are computable. In particular my work has concentrated on the combinatorial properties, in terms of algorithmic content, of computable orderings. Recent work of note has been joint research on the rigidity properties of a specific common class of computable linear orderings, as also an investigation into the algorithmic complexity required to linearise computable partial orderings with certain properties (such as computable well foundedness).
|Address||:||University of Leeds
School of Mathematics
Leeds LS2 9JT
|Tel||:||+44 (0)113 34 31619