Harvard Theory of Computation Seminar

Proof of Church’s Thesis

Yuri Gurevich, Microsoft Research

Place and Time: Monday, December 8, 2008, Maxwell Dworkin 319

Refreshments at 2:30pm, talk at 3:00pm

ABSTRACT

Church’s Thesis asserts that every effectively calculable numerical function is recursive. Why we believe the thesis? Careful analysis shows that existing argumentation is insufficient. Kurt Goedel surmised that “it might be possible … to state axioms which embody the generally accepted properties of [effective calculability], and to do something [to prove the thesis] on that basis”. That is exactly what we have done. This is joint work with Nachum Dershowitz of Tel Aviv University.

Bio: 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.