The Church-Turing Thesis: Foundations and Recent Developments

Google Tech Talk
June 8, 2009

ABSTRACT

Presented by Yuri Gurevich.

The Church-Turing thesis is one of the foundations of computer science. The thesis heralded the dawn of the computer revolution by enabling the construct of the universal Turing machine which led the way, at least conceptually, to the von Neumann architecture and first electronic computers. One way to state the Church-Turing thesis is as follows:

A Turing Machine computes every numerical function that is computable by means of a purely mechanical procedure.

It is that remarkable and a priori implausible characterization that underlies the ubiquitous applicability of digital computers. But why do we believe the thesis? Careful analysis shows that the existing arguments are insufficient. Kurt Gödel surmised that it might be possible to state axioms which embody the generally accepted properties of computability, and to prove the thesis on that basis. That is exactly what we did in a recent paper with Nachum Dershowitz of Tel Aviv University.

Beyond our proof, the story of the Church-Turing thesis is fascinating and scattered in specialized and often obscure publications. I will try to do justice to that intellectual drama.

Yuri Gurevich is Principal Researcher at Microsoft Research in Redmond, WA. He is also Prof. Emeritus at the University of Michigan, ACM Fellow, Guggenheim Fellow, a member of Academia Europaea, and Dr. Honoris Causa of a couple of universities.