Research Fellows Directory
Dr Andrew Lewis
London School of Economics & Political Science
Computability is an area of mathematics in which we formally consider those tasks, procedures and functions which can be achieved by an algorithmic process. We consider which functions can be computed by computer programs and which cant. In some sense, most functions are not algorithmically achievable. A famous example along these lines is the incompleteness theorem of Godel who showed, roughly speaking, that there is no algorithm which will decide whether or not any given statement about the natural numbers (0,1,2,...) is true when we consider these numbers ordered in the standard way, and when we consider the standard operations of addition and multiplication (so long as the language in which we are allowed to express these statements is reasonably expressive).
Amongst the functions which are not computable, we can also consider DEGREES of non-computability. Some functions are not computable, but may be fairly close to being computable -- it may be possible to approximate them, for example. Still other functions may be much harder to compute than that. The structure of these degrees of computability is called the Turing degrees. My research looks to answer some fundamental questions concerning this structure, which mathematicians have been trying to solve since midway through the 20th century.