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

(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:

- a mathematical model of a human making a calculation, namely the Turing machine;
- the idea of a universal machine that can mimic all other machines, namely a general programmable computer; and
- 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