Step by recursive step: Church's analysis of effective calculability

Bulletin of Symbolic Logic 3 (2):154-180 (1997)
  Copy   BIBTEX


Alonzo Church's mathematical work on computability and undecidability is well-known indeed, and we seem to have an excellent understanding of the context in which it arose. The approach Church took to the underlying conceptual issues, by contrast, is less well understood. Why, for example, was "Church's Thesis" put forward publicly only in April 1935, when it had been formulated already in February/March 1934? Why did Church choose to formulate it then in terms of Gödel's general recursiveness, not his own λ -definability as he had done in 1934? A number of letters were exchanged between Church and Paul Bernays during the period from December 1934 to August 1937; they throw light on critical developments in Princeton during that period and reveal novel aspects of Church's distinctive contribution to the analysis of the informal notion of effective calculability. In particular, they allow me to give informed, though still tentative answers to the questions I raised; the character of my answers is reflected by an alternative title for this paper, Why Church needed Gödel's recursiveness for his Thesis. In Section 5, I contrast Church's analysis with that of Alan Turing and explore, in the very last section, an analogy with Dedekind's investigation of continuity



    Upload a copy of this work     Papers currently archived: 94,452

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Step by Recursive Step: Church’s Analysis of Effective Calculability.Wilfried Sieg - 2006 - In Adam Olszewski, Jan Wolenski & Robert Janusz (eds.), Church's Thesis After 70 Years. Ontos Verlag. pp. 456-490.
Kalmár's Argument Against the Plausibility of Church's Thesis.Máté Szabó - 2018 - History and Philosophy of Logic 39 (2):140-157.
Godel on computability.W. Sieg - 2006 - Philosophia Mathematica 14 (2):189-207.
The collected works of Alonzo Church.Alonzo Church - 2019 - Cambridge, Massachusetts: The MIT Press. Edited by Tyler Burge & Herbert B. Enderton.
Remarks on the development of computability.Stewart Shapiro - 1983 - History and Philosophy of Logic 4 (1-2):203-220.
Church's Thesis and the Conceptual Analysis of Computability.Michael Rescorla - 2007 - Notre Dame Journal of Formal Logic 48 (2):253-280.
The mathematical work of S. C. Kleene.J. R. Shoenfield & S. C. Kleene - 1995 - Bulletin of Symbolic Logic 1 (1):8-43.


Added to PP

89 (#189,456)

6 months
10 (#396,727)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Wilfried Sieg
Carnegie Mellon University

References found in this work

On Computable Numbers, with an Application to the Entscheidungsproblem.Alan Turing - 1936 - Proceedings of the London Mathematical Society 42 (1):230-265.
Introduction to Metamathematics.H. Rasiowa - 1954 - Journal of Symbolic Logic 19 (3):215-216.
An Unsolvable Problem of Elementary Number Theory.Alonzo Church - 1936 - Journal of Symbolic Logic 1 (2):73-74.
A note on the entscheidungsproblem.Alonzo Church - 1936 - Journal of Symbolic Logic 1 (1):40-41.

View all 24 references / Add more references