Cleland on Church’s Thesis and the Limits of Computation

Even though Church’s thesis is widely accepted among mathematicians, it is nonetheless controversial. In this paper, we argue against the position of [Cleland 1993], which defends that Church s thesis must be rejected because the limits of computation depend upon the physical structure of the world. We first give a brief overview of Church’s thesis and then we present Cleland s argument. We then propose a critical analysis of Cleland s argu­ment, which will involve some conceptual distinctions regarding the notion of computability, and finally we will show that the limits of computation are not physical but logical. In short, we argue that computation is limited by the fact that an effective procedure must be described in a finite way.