The Church-Turing Thesis: Story and Recent Progress
The Church-Turing Thesis: Story and Recent Progress
Dr. Yuri Gurevich
Tuesday, January 20, 2009
Time: 6:00pm
Microsoft Research Building 99
Room 1919
14820 NE 36th Street
Redmond, Washington 98052
Presented by the Association for the Advancement of Artificial Intelligence (AAAI) Greater Seattle Region
Introduction: Dr. Eric Horvitz, AAAI President
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 that embody the generally accepted properties of computability, and to prove the thesis on that basis. That is exactly what Yuri Gurevich did in a recent paper with Nachum Dershowitz of Tel Aviv University.
Beyond their proof, the story of the Church-Turing thesis is fascinating and scattered in specialized and often obscure publications. Dr. Gurevich will review that intellectual drama.
Yuri Gurevich is Principal Researcher at Microsoft Research in Redmond, WA. He is also Professor Emeritus at the University of Michigan, ACM Fellow, Guggenheim Fellow, a member of Academia Europaea, and Dr. Honoris Causa of two universities.