What can we compute? A history of the Church-Turing Hypothesis

Photograph of John Tucker

John Tucker

(Swansea University)

In 1936, motivated by the philosophical problem of what are the limits to human knowledge, Alan Turing wrote his wonderful paper the nature of computation; he was 24 years old. In it is to be found three intellectual innovations:
  1. a mathematical model of a human making a calculation, namely the Turing machine;
  2. the idea of a universal machine that can mimic all other machines, namely a general programmable computer; and
  3. the discovery of a computation that is provably impossible to perform.
In this lecture I will look at one of the many legacies of this work: the hypothesis that anything that can be calculated can be calculated by a Turing machine. This hypothesis is plays an important role in computer science, mathematics, neuroscience, and philosophy of science. I will concentrate on how the thesis arose and on its generalisations in algebra, programming and physics.

This talk is a joint-talk with the Scientists, Science, and Society seminars, as well as celebrating the Alan Turing Centenary.
Friday 30th November 2012, 15:00
Robert Recorde Room
Department of Computer Science