Church's Thesis
Guram Bezhanishvili · Mathematical Association of America eBooks · 2009
Introduction In this project we will learn about both primitive recursive and general recursive functions. We will also learn about Turing computable functions, and will discuss why the class of general recursive functions coincides with the class of Turing computable functions. We will introduce the effectively calculable functions, and the ideas behind Alonzo Church's (1903–1995) proposal to identify the class of effectively calculable functions with the class of general recursive functions, known as “Church's thesis.” We will analyze Kurt Gödel's (1906–1978) initial rejection of Church's thesis, together with the work of Alan Turing (1912–1954) that finally convinced Gödel of the validity of Church's thesis. We will learn much of this by studying and working with primary historical sources by Gödel, Stephen Cole Kleene (1909–1994), and Turing. We begin by asking the following question: What does it mean for a function f to be effectively calculable ? Obviously if we can find an algorithm to calculate f , then f is effectively calculable. For example, the famous Euclidean algorithm tells us that the binary function producing the greatest common divisor of two integers is effectively calculable. But what if we can not find an algorithm that calculates f ? The reason could be that there is no algorithm calculating f ; or it could be that f is effectively calculable but we were not successful in finding an algorithm. Thus, it is evident that we need better means to identify effectively calculable functions.