Andre Nies (University of Auckland) visited our Department to present his seminar on “Interactions of computability and randomness”. He also kindly took time out with Andy Lewis-Pye (LSE) to answer a few questions on his research, the future of algorithmic randomness and incorporating classical music into his presentations.
You’ve been doing some fascinating work on the interactions between computability and randomness. In layman’s terms, could you tell us something about the goals and conclusions of your research?
Randomness is an intuitive notion most humans have. I have tracked down the word for randomness in about 30 languages, and in most cases the stem is different, which shows that different cultures arrived at the concept independently. The first goal of the research was to find mathematical definitions of randomness, similar to the mathematical definitions of computability from the 1940s. Martin-Loef probably had the first satisfying definition of randomness; others followed, some weaker and some stronger.
An outcome of the research is that complexity of infinite bit sequences can be understood through randomness; for instance the K-trivial sets are far from random, and at the same time very close to computable.
Another outcome is that one can understand randomness by connecting it to various areas of mathematics. For instance, a notion, different from Martin-Loef’s, is defined via betting strategies, and has deep connections to computable analysis, namely differentiability of effective non-decreasing functions. After my LSE talk, I got lots of interesting feedback from people in other areas, especially topology.
What directions do you predict for the study of algorithmic randomness over the next decade or so?
I expect a fuller understanding of the K-trivials- just like in physics “there’s lots of space down there” (Feynman), and they exhibit interesting behaviour when it comes to relative complexity. I also expect more interactions with other areas of mathematics. Two workshops next year, in Luminy and the CMO (BIRS/Oaxaca) are in part dedicated to the interaction with ergodic theory.
Do you think that the understanding of randomness developed within algorithmic information theory might end up having scientific applications outside mathematics? Are applications something you worry about, or do you think the best approach is to follow the mathematically interesting questions?
Definitely. I haven’t yet worked on applications, but will be glad to see them. The area is centred on infinite sequences of bits. In my opinion, infinite objects are not the objects of study in the physical sciences, but can be a natural theoretical way of looking at very large objects. Algorithmic information theory as a theory of compression for finite objects is relevant in big data and computational biology.
You are a keen collaborator. Could you tell us something about your approach to collaboration?
I listen to people, to find out things I couldn’t do myself. I don’t sit on a high chair. I want to know what they THINK, even if it can be difficult to bear. I much enjoy doing fun stuff with my co-workers. Last summer in New Zealand, some of us went to do the Heaphy Track on the South Island, four days in the wild.
You’ve been based in New Zealand for a while now. Does the academic community there have a distinctively different flavour than in Europe or the USA?
Not much. They may be more relaxed, and they do like to get together in nice settings away from the city. I’ve just started running a research centre close to the beach – its first summer has been quite successful, with several small groups visiting, and three new projects in widely spread, interesting areas.
Outside mathematics, what are your interests?
I still love music, as well as travel and outdoor sports. My favourite composers are Bach, Chopin, and Arvo Part (I’ve used his Canon to explain K-triviality in a recent talk). The latest country that really impressed me was Iceland. As for sport, I like track running, cycling and swimming. I love to combine exploring with physical exercise.