TIME: 1:30 -- 2:20 pm, Tuesday, April 7, 2009

PLACE: CSE 503

SPEAKER: Yuri Gurevich, Microsoft Research

TITLE: Proof of Church's Thesis

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