Skip to content


Andrew Lewis

Dr Andrew Lewis

Dr Andrew Lewis

Research Fellow

Interests and expertise (Subject groups)

Grants awarded

On computability and algorithmic randomness

Scheme: University Research Fellowship

Organisation: London School of Economics & Political Science

Dates: Oct 2012-Sep 2015

Value: £275,560.66

Summary: My research concerns issues in and around computability, complexity science, optimisation and learning. The questions with which I am concerned often sit at the interface between mathematical logic and computer science, with links also to statistical mechanics and population genetics. In computability we are concerned with the fundamental question as to which tasks can be algorithmically solved. We are concerned, in other words, with understanding the limits of computer programs -- what exactly can they do for us, and what tasks are there which a computer programme will never be able to achieve? Famous results by Godel, Turing and others from the 1930s established some basic limits, such as the fact that no computer programme will ever exist which is capable of telling us which precisely which mathematical theorems are true. Given these results, it then becomes important to consider the notion of *relative* computation. Now we consider computations which do not happen in isolation but rather consists of a back and forth process of information exchange with the world around them. Well inside the world of computable tasks, my most recent project then concerns a major problem in population genetics, which has recently attracted significant attention in the world of computer science. The basic task is to explain the predominance of sexual rather than asexual reproduction in higher organisms. Working with Antonio Montalban (Berkeley), we have developed a model and techniques for its analysis, which demonstrate the basic mechanisms by which sex acts as a more efficient optimiser of mean fitness (in contexts where fitness contributions from individual genes are combined additively). This work should lead to a deeper understanding of contexts in which population based algorithms can be fruitfully applied to optimisation and learning processes.

On computability and algorithmic randomness

Scheme: University Research Fellowship

Organisation: University of Leeds

Dates: Oct 2007-Sep 2012

Value: £422,918.40

Summary: 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.

Was this page useful?
Thank you for your feedback
Thank you for your feedback. Please help us improve this page by taking our short survey.