14 September 2004 The Church-Turing Theses
817R Cathedral of Learning
Abstract: The Church-Turing thesis states
that every number-theoretic function which is effectively computable
is also Turing machine computable (recursive). But what is
"effectively computable"? I will discuss different understandings
of the notion, and consider their implications for the status of
the thesis in respect to truth and provability.