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

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

Authors
Wilfried Sieg
Carnegie Mellon University
Abstract
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
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.2307/421012
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 45,727
Through your library

References found in this work BETA

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.Stephen Cole Kleene - 1954 - Journal of Symbolic Logic 19 (3):215-216.
Introduction to Mathematical Logic.ALONZO CHURCH - 1956 - Journal of Symbolic Logic 23 (3):362-362.

View all 22 references / Add more references

Citations of this work BETA

The Physical Church-Turing Thesis: Modest or Bold?Gualtiero Piccinini - 2011 - British Journal for the Philosophy of Science 62 (4):733-769.
Alan Turing and the Mathematical Objection.Gualtiero Piccinini - 2003 - Minds and Machines 13 (1):23-48.
Effective Computation by Humans and Machines.Shagrir Oron - 2002 - Minds and Machines 12 (2):221-240.
Proving Church's Thesis.Robert Black - 2000 - Philosophia Mathematica 8 (3):244--58.
Kurt Gödel and Computability Theory.Richard Zach - 2006 - In Arnold Beckmann, Ulrich Berger, Benedikt Löwe & John V. Tucker (eds.), Logical Approaches to Computational Barriers. Second Conference on Computability in Europe, CiE 2006, Swansea. Proceedings. Berlin: Springer. pp. 575--583.

View all 16 citations / Add more citations

Similar books and articles

Church's Thesis: Prelude to a Proof.Janet Folina - 1998 - Philosophia Mathematica 6 (3):302-323.
Witness and Service to the World. Discovering Protestant Church Renewal in Europe.Henning Theißen - 2011 - Neue Zeitschrift für Systematicsche Theologie Und Religionsphilosophie 53 (2):225-239.
Computability and Recursion.Robert I. Soare - 1996 - Bulletin of Symbolic Logic 2 (3):284-321.
SAD Computers and Two Versions of the Church–Turing Thesis.Tim Button - 2009 - British Journal for the Philosophy of Science 60 (4):765-792.
Church's Thesis and the Conceptual Analysis of Computability.Michael Rescorla - 2007 - Notre Dame Journal of Formal Logic 48 (2):253-280.
Is the Church-Turing Thesis True?Carol E. Cleland - 1993 - Minds and Machines 3 (3):283-312.
The Church-Turing Thesis.B. Jack Copeland - 2008 - In Edward N. Zalta (ed.), The Stanford Encyclopedia of Philosophy. The Metaphysics Research Lab, Stanford University.
How Not To Use the Church-Turing Thesis Against Platonism.R. Urbaniak - 2011 - Philosophia Mathematica 19 (1):74-89.

Analytics

Added to PP index
2009-01-28

Total views
40 ( #222,434 of 2,280,975 )

Recent downloads (6 months)
3 ( #421,058 of 2,280,975 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature