An Interview with Robert Soare

University of Chicago’s Robert Soare, the Paul Snowden Russell Distinguished Service Professor of Mathematics and Computer Science, offers his reflections on Alan Turing. Interviewed by Arefin Huq

DOI: 10.1145/2090276.2090284

AREFIN HUQ: Your upcoming book is entitled, Computability Theory and Applications, and it’s subtitled, “The art of classical computability.” Why did you choose that title?

ROBER T SOARE: Mathematicians value work on the basis of beauty. It has to be correct, but the question is: Is it beautiful? Is it a beautiful theorem, a beautiful proof? At the University of Chicago no one asks me to do the mathematics of building bridges on a deadline. I choose the problems that I work on, and I choose problems for my students, and they work on the things they enjoy doing. We do it because we hope to solve important problems but we do it also because it’s beautiful. So the subtitle, “The art of classical computability,” is supposed to represent this thought.

Photograph by Olin Mills

Robert Soare

AH: What makes Turing’s model of computation so compelling?

RS: Why do we give so much credit to
Turing? His advisor, Alonzo Church, was
already a professor before Turing even
started out, and Church proposed one
definition of computable function in 1934,
the lambda-definable functions, and
another one in 1935. Church got it right,
twice, and he got it first. He got it right in
the sense that he proposed a model which
later proved to be correct. Turing came on
the scene only in 1936, when he published
his paper after Church’s paper was already
announced and published. And yet if you
pick up any book on computability now
you’ll see a description of a Turing machine.
You won’t see the lambda-definable
functions of Church and you won’t see the
recursive functions of Herbrand-Gödel, but
you will see Turing’s model because it is
easy to understand. That’s the first part.