Abstract

For a general formulation of the undecidability and incompleteness theorems one has to characterize precisely the notion of formal system. Such a characterization is provided by the proposal to identify the intuitive concept of effectively calculable function with that of partial recursive function. A proper understanding of this identification, which is known under the name of "Church's thesis", is crucial for a philosophical assessment of these metamathematical results. The undecidability and incompleteness theorems suggest one major but certainly not the only reason for interest in Church's thesis. The thesis provides a sharp characterization of a concept that has played an epistemologically motivated role in many logical and foundational investigations and that has been appealed to in methodological discussions concerning computational approaches in cognitive psychology. ;In spite of these various motives of interest a detailed philosophical analysis of the meaning and the epistemological status of Church's thesis has been neglected; a thorough and balanced presentation of arguments for it is lacking. This seems to me to be due to two widespread views of the thesis, both tending to discourage analytical work. According to the first of these views, Church's thesis is unproblematic because the classical arguments for the identification are convincing. According to the second view, it is hopeless to try to evaluate the adequacy of a proposed mathematical characterization of effectiveness, because the intuitive notion is too vague. The analysis undertaken in this thesis conflicts with both views. ;I All classical arguments for Church's thesis, including Turing's, have unconvincing aspects. ;II Some generalizations of Turing's work show that unconvincing aspects of Turing's argument can be dispensed with and provide conceptually significant contributions to the problem of a "natural" mathematical characterization of the mechanically calculable functions. ;III One can isolate meanings of effectiveness conceptually more inclusive than mechanical calculability and distinguish between corresponding interpretations of Church's thesis. ;The analytical work supporting these claims bears significantly on the philosophical issues mentioned above: it plays a crucial role in a philosophical evaluation of the undecidability and incompleteness theorems and in a clarification of the conceptual background of computational approaches in cognitive psychology