Abstract
‘Church’s Thesis’ (CT hereinafter) is the statement that a function of natural numbers is effectively computable if and only if that function is recursive. Like any biconditional, CT may be regarded as a conjunction of two conditionals. The arguments treated in this paper have been advanced in support of the so-called ‘problematic conjunct’ of CT, viz. that all effectively computable functions are recursive. When I use CT then, I shall intend the problematic conjunct. So far as I have been able to determine, no one thinks that CT is amenable to anything like a conclusive proof of its truth, though I think that everyone recognizes that it could, at least in principle, be refuted by a suitable counterexample. Even Kreisel, who takes CT to be a statement of intuitionistic mathematics, nowhere considers the possibility that CT might be a theorem, though he speaks of ‘finding axioms inconsistent with’ CT.1 Perhaps we ought to be surprised, or at least puzzled by this fact, since some of the arguments which have been given for CT look like deductive arguments from premises that are supposed to be beyond dispute. Of course, if these arguments really were deductively valid and dependent only upon indisputable premises, the propounders of the arguments would be likely to show more confidence in them than anyone has done.
This paper is adapted from Chapter IV of my Ph.D. Dissertation Church’s Thesis and Philosophy. Special thanks are due to my advisors, Professor Raymond Nelson and Professor Howard Stein.
This is a preview of subscription content, log in via an institution.
Buying options
Tax calculation will be finalised at checkout
Purchases are for personal use only
Learn about institutional subscriptionsPreview
Unable to display preview. Download preview PDF.
References
G. Kreisel, ‘Mathematical Logic’ in Lectures on Modern Mathematics (ed. by T. L. Saaty), Wiley, New York, 1965, vol. in, p. 147.
Hao Wang, Survey of Mathematical Logic, Science Press, Peking 1964, p. 88.
S. C. Kleene, Introduction to Metamathematics, Van Nostrand, Princeton, 1952, p. 348. Cf. S. C. Kleene, Mathematical Logic, Wiley, New York, 1967, pp. 240–1 n. 171 and Kleene (1952), p. 352.
Kleene (1952), pp. 319–20.
Kleene (1952), p. 320.
Kreisel op. cit., p. 144.
A. M. Turing, ‘On Computable Numbers, with an Application to the Entscheidungs-problem’, reprinted in The Undecidable (ed. by M. Davis), Raven Press, Hewlett, New York, 1965, pp. 135ff. Cf. Kleene (1952), pp. 377ff.
Kleene (1952), pp. 379–80.
Kleene (1952), p. 380.
Alonzo Church, ‘An Unsolvable Problem of Elementary Number Theory’, reprinted in The Undecidable (ed. by M. Davis), pp. 101–102. Cf. Kleene (1952), pp. 322–3.
Kleene (1952), p. 323, does essentially this when he says that we may regard the ordered pair (x, the first expression in the sequence) as an axiom of a first order theory
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1973 D. Reidel Publishing Company, Dordrecht, Holland
About this chapter
Cite this chapter
Thomas, W.J. (1973). Doubts about Some Standard Arguments for Church’s Thesis. In: Bogdan, R.J., Niiniluoto, I. (eds) Logic, Language, and Probability. Synthese Library, vol 51. Springer, Dordrecht. https://doi.org/10.1007/978-94-010-2568-3_5
Download citation
DOI: https://doi.org/10.1007/978-94-010-2568-3_5
Publisher Name: Springer, Dordrecht
Print ISBN: 978-94-010-2570-6
Online ISBN: 978-94-010-2568-3
eBook Packages: Springer Book Archive