[Pl-seminar] Gurevich at Harvard, M 12/8

[Mitchell Wand]

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.