Axioms for Computability: Do They Allow a Proof of Church’s Thesis?
This contribution consists of a previously published paper, Church without dogma: axioms for computability, and a long Postscriptum, Is there a proof of Church’s Thesis?. The paper appeared in S.B. Cooper, B. Löwe, A. Sorbi, (eds), New Computational Paradigms: Changing conceptions of what is computable, Springer, 2007; it is reprinted here with the permission of Springer. The new Postscriptum gives a detailed analysis of the paper A natural axiomatization of computability and proof of Church’s Thesis by N. Dershowitz and Y. Gurevich; it is argued that it does not contain a proof of Church’s Thesis.
Church’s and Turing’s theses assert dogmatically that an informal notion of effective calculability is adequately captured by a particular mathematical concept of computability. I present analyses of calculability that are embedded in a rich historical and philosophical context, lead to precise concepts, and dispense with theses…
