2018 Rutherford Medal: Solving ‘Can’t compute’ and is that random sequence really random?

The Rutherford Medal is the highest honour awarded by the Society for an exceptional contribution to advancing and promoting knowledge for the benefit of New Zealand.

Professor Rod Downey, of Victoria University of Wellington, is an internationally recognised logician known for his research into computability—how can mathematical processes be algorithmically implemented either in theory or practice — and the study of randomness.

One of Rod’s specialities is recursion (computability) theory, which is a branch of mathematical logic dealing with the fundamental limits of computation. This research area explores the extent to which mathematical operations and processes can be carried out algorithmically (by a computer) and how difficult they are to compute in terms of various measures such as the use of computer memory or time.

Professor Downey says an algorithm is like a recipe. “A good cake recipe would be one that makes a good cake. Mathematically a good algorithm would be one that uses less resources, runs faster and uses less memory.”

Rod founded the field of algorithm design called parameterised complexity with co-author Michael Fellows Hon FRSNZ, which has shown that many apparently intractable computations become feasible once fixed values are given to certain parameters, such as the amount of input data to be used or the size of object to be computed. This subject has now developed into an important new branch of theoretical computer science, which has its own international conferences, books and special issues of journals, with applications to many areas. 

It has been applied to numerous fields and projects that are as diverse as studying deafness in aboriginal children in Australia, the effects of radiation on DNA, reconstructing the ‘tree of life’ (phylogenetic analysis), studying the evolution of European languages, efficient design of distributing donated food to charities, information-based medicine and many others.

Rod also initiated a comprehensive development in the field of algorithmic randomness, publishing a large research publication in 2010 on the topic that gives a unifying treatment of several related but historically separate approaches to the question of what makes a sequence random. Studying randomness can help determine complex questions like ‘is this piece of DNA similar to this other one?’ or ‘did this composer plagiarise another composer?’

He was invited to give an address at the 2006 International Congress of Mathematicians, the first New Zealand-based person invited to do so, and in 2018 he was invited to be the prestigious Gödel Lecturer for the Association for Symbolic Logic.

In awarding this medal, in addition to his outstanding scientific contribution, the medal selection committee noted his outstanding record as a research leader and mentor.

Rod Downey with his Rutherford Medal

On receiving the Rutherford Medal, Rod said he was “honoured and somewhat startled”.

“The first recipient of this award was the great Kiwi mathematician Sir Vaughan Jones after he won the Fields Medal. Thus, it is especially rewarding to receive this award as a mathematician and theoretical computer scientist. The mathematical landscape in New Zealand is truly vibrant, and this is particularly true at Victoria University of Wellington.”

In 2017 Rod was made a Fellow of the Institute for Mathematical Sciences and also received the Humboldt Prize from the Humboldt Foundation. He has received the Shoenfield Prize from the Association for Symbolic Logic twice (in 2010 for an article and in 2016 for a book). He received the Hector Medal from Royal Society Te Apārangi in 2011, a James Cook Research Fellowship in 2008-2010 and in 2017 a Festschrift and a month-long programme in Singapore were held by his colleagues and students in his honour.

Other fellowships include Founding Fellow of Institute of Combinatorics and its Applications (1991), Fellow of Royal Society of New Zealand (1996), Fellow of the Association for Computing Machinery (2008), Fellow of the American Mathematical Society (2012), Fellow of the Newton Institute (Cambridge) for the Alan Turing Programme (2012) and Fellow of the Australian Mathematical Society (2013).

Rutherford Medal:

For an exceptional contribution to the advancement and promotion of knowledge of science and technology for the benefit of New Zealand society. This medal is the highest honour awarded by Royal Society Te Apārangi.

Citation:

To Rodney Graham Downey for his pre-eminent revolutionary research into computability, including development of the theory of parameterised complexity and the algorithmic study of randomness