Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-25T14:21:41.212Z Has data issue: false hasContentIssue false
  • English
  • Français

Step by Recursive Step: Church's Analysis of Effective Calculability

Published online by Cambridge University Press:  15 January 2014

Wilfried Sieg
Wilfried Sieg*
Affiliation:
Department of Philosophy, Carnegie Mellon University, Pittsburgh, PA 15213-3890, USA.E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

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.

Type
Research Article
Information
Bulletin of Symbolic Logic , Volume 3 , Issue 2 , June 1997 , pp. 154 - 180
Copyright
Copyright © Association for Symbolic Logic 1997

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1] Bernays, Paul, Logical calculus, The Institute for Advanced Studies, Princeton, 1935–1936, notes by Prof. Bernays with assistance of Mr. F. A. Ficken.Google Scholar
[2] Church, Alonzo, Alternatives to Zermelo's assumption, Transactions of the American Mathematical Society, vol. 29 (1927), pp. 178–208, Ph.D. thesis, Princeton.CrossRefGoogle Scholar
[3] Church, Alonzo, On the law of the excluded middle, Bulletin of the American Mathematical Society, vol. 34 (1928), pp. 75–78.Google Scholar
[4] Church, Alonzo, A set of postulates for the foundation of logic, part I, Annals of Mathematics, vol. 33 (1932), no. 2, pp. 346–66.Google Scholar
[5] Church, Alonzo, A set of postulates for the foundation of logic, part II, Annals of Mathematics, vol. 34 (1933), no. 2, pp. 839–64.CrossRefGoogle Scholar
[6] Church, Alonzo, The Richard paradox, American Mathematical Monthly, vol. 41 (1934), pp. 356–61.Google Scholar
[7] Church, Alonzo, A proof of freedom from contradiction, Proceedings of the National Academy of Sciences, vol. 21 (1935), pp. 275–81.CrossRefGoogle ScholarPubMed
[8] Church, Alonzo, An unsolvable problem of elementary number theory, Bulletin American Mathematical Society, vol. 41 (1935), pp. 332–3.Google Scholar
[9] Church, Alonzo, A note on the Entscheidungsproblem, Journal of Symbolic Logic, vol. 1 (1936), pp. 40–1, Corrections, Journal of Symbolic Logic , vol. 1 (1936), pp. 101–2.Google Scholar
[10] Church, Alonzo, An unsolvable problem of elementary number theory, American Journal of Mathematics, vol. 58 (1936), pp. 345–63.Google Scholar
[11] Church, Alonzo, Review of [54], Journal of Symbolic Logic, vol. 2 (1937), no. 1, p. 43.CrossRefGoogle Scholar
[12] Church, Alonzo, Review of [63], Journal of Symbolic Logic, vol. 2 (1937), no. 1, pp. 42–3.CrossRefGoogle Scholar
[13] Church, Alonzo, Introduction to mathematical logic, vol. I, Princeton University Press, Princeton, 1956.Google Scholar
[14] Church, Alonzo and Kleene, Stephen C., Formal definitions in the theory of ordinal numbers, Bulletin of the American Mathematical Society, vol. 41 (1935), p. 627.Google Scholar
[15] Church, Alonzo and Kleene, Stephen C., Formal definitions in the theory of ordinal numbers, Fundamenta Mathematicae, vol. 28 (1936), pp. 11–21.CrossRefGoogle Scholar
[16] Church, Alonzo and Rosser, J. Barkley, Some properties of conversion, Bulletin of the American Mathematical Society, vol. 41 (1935), p. 332.Google Scholar
[17] Church, Alonzo and Rosser, J. Barkley, Some properties of conversion, Transactions of the American Mathematical Society, vol. 39 (1936), pp. 472–82.Google Scholar
[18] Davis, Martin, The undecidable, Raven Press, Hewlett, New York, 1965.Google Scholar
[19] Davis, Martin, Why Gödel didn't have Church's thesis, Information and Control, vol. 54 (1982), pp. 3–24.CrossRefGoogle Scholar
[20] Davis, Martin, American logic in the 1920s, this Bulletin, vol. 1 (1995), no. 3, pp. 273–8.Google Scholar
[21] Dawson, John W., Logical dilemmas—the life and work of Kurt Gödel, A. K. Peters, Wellesley, 1997.Google Scholar
[22] Dedekind, Richard, Stetigkeit und irrationale Zahlen, Vieweg, Braunschweig, 1872.Google Scholar
[23] Dedekind, Richard, Was sind und was sollen die Zahlen?, Vieweg, Braunschweig, 1888.Google Scholar
[24] Enderton, Herb, In memoriam: Alonzo Church, this Bulletin, vol. 1 (1995), no. 4, pp. 486–88.Google Scholar
[25] Feferman, Solomon, Turing in the land of O(z), The universal Turing machine (Herken, Rolf, editor), Oxford University Press, Oxford, 1988, pp. 113–47.Google Scholar
[26] Gandy, Robin, The confluence of ideas, The universal Turing machine (Herken, Rolf, editor), Oxford University Press, Oxford, 1988, pp. 55–111.Google Scholar
[27] Gödel, Kurt, The present situation in the foundations of mathematics, Collected works III, Oxford University Press, Oxford, 1933, pp. 45–53.Google Scholar
[28] Gödel, Kurt, On undecidable propositions of formal mathematical systems, Collected works I, Oxford University Press, Oxford, 1934, pp. 346–371.Google Scholar
[29] Gödel, Kurt, Review of [5], Collected works I, Oxford University Press, Oxford, 1934, pp. 381–3.Google Scholar
[30] Gödel, Kurt, On the length of proofs, Collected works I, Oxford University Press, Oxford, 1936, pp. 397–9.Google Scholar
[31] Gödel, Kurt, Review of [7], Collected works I, Oxford University Press, Oxford, 1936, pp. 399–401.Google Scholar
[32] Gödel, Kurt, Remarks before the Princeton bicentennial conference on problems in mathematics, Collected works II, Oxford University Press, Oxford, 1946, pp. 150–3.Google Scholar
[33] Gödel, Kurt, Collected works I, Oxford University Press, Oxford, 1986.Google Scholar
[34] Gödel, Kurt, Collected works II, Oxford University Press, Oxford, 1990.Google Scholar
[35] Gödel, Kurt, Collected works III, Oxford University Press, Oxford, 1995.Google Scholar
[36] Hilbert, David, Natur und mathematisches Erkennen, 1919, lecture given in the Winter term 1919, the notes were written by Paul Bernays; reprint by the Mathematical Institute of the University Göttingen, 1989.Google Scholar
[37] Hilbert, David and Bernays, Paul, Grundlagen der Mathematik I, Springer-Verlag, Berlin, 1934.Google Scholar
[38] Hilbert, David and Bernays, Paul, Grundlagen der Mathematik II, Springer-Verlag, Berlin, 1939.Google Scholar
[39] Kleene, Stephen C., Proof by cases in formal logic, Annals of Mathematics, vol. 35 (1934), pp. 529–44.Google Scholar
[40] Kleene, Stephen C., General recursive functions of natural numbers, Bulletin of the American MathematicalSociety, vol. 41 (1935), p. 489.Google Scholar
[41] Kleene, Stephen C., λ-definability and recursiveness, Bulletin of the American Mathematical Society, vol. 41 (1935), p. 490.Google Scholar
[42] Kleene, Stephen C., A theory of positive integers in formal logic, American Journal of Mathematics, vol. 57 (1935), pp. 153–73, 219–44, the story behind this paper is described in [47, pp. 57–58]; it was first submitted on October 9, 1933; its revised version was re-submitted on June 13, 1934.Google Scholar
[43] Kleene, Stephen C., General recursive functions of natural numbers, Mathematische Annalen, vol. 112 (1936), pp. 727–42.Google Scholar
[44] Kleene, Stephen C., λ-definability and recursiveness, Duke Mathematics Journal, vol. 2 (1936), pp. 340–53, [40] and [41] are abstracts of these two papers and were received by the American Mathematical Society on 07 1, 1935.CrossRefGoogle Scholar
[45] Kleene, Stephen C., A note on recursive functions, Bulletin of the American Mathematical Society, vol. 42 (1936), pp. 544–6.Google Scholar
[46] Kleene, Stephen C., Introduction to metamathematics, Wolters-Noordhoff Publishing, Groningen, 1952.Google Scholar
[47] Kleene, Stephen C., Origins of recursive function theory, Annals of Historical Computing, vol. 3 (1981), no. 1, pp. 52–66.Google Scholar
[48] Kleene, Stephen C. and Rosser, J. Barkley, The inconsistency of certain formal logics, Bulletin of the American Mathematical Society, vol. 41 (1935), p. 24, this abstract was received by the American Mathematical Society on 11 16, 1934.Google Scholar
[49] Kleene, Stephen C. and Rosser, J. Barkley, The inconsistency of certain formal logics, Annals of Mathematics, vol. 36 (1935), no. 2, pp. 630–6.Google Scholar
[50] Mendelson, Elliott, Second thoughts about Church's thesis and mathematical proofs, The Journal of Philosophy, vol. 87 (1990), no. 5, pp. 225–33.Google Scholar
[51] Mundici, Daniele and Sieg, Wilfried, Paper machines, Philosophia Mathematica, vol. 3 (1995), pp. 5–30.Google Scholar
[52] Odifreddi, Piergiorgio, Kreisel's Church, Kreiseliana (Odifreddi, P., editor), A. K. Peters, Wellesley, 1996, pp. 389–415.Google Scholar
[53] Pepis, Józef, Ein Verfahren der mathematischen Logik, Journal of Symbolic Logic, vol. 3 (1938), pp. 61–76, reviews of some of his papers appeared in the Journal of Symbolic Logic , vol. 2, p. 84; vol. 3, pp. 160–1; vol. 4, p. 93.Google Scholar
[54] Post, Emil, Finite combinatory processes. Formulation I, Journal of Symbolic Logic, vol. 1 (1936), pp. 103–5.Google Scholar
[55] Rosser, J. Barkley, A mathematical logic without variables, Annals of Mathematics, vol. 36 (1935), no. 2, pp. 127–50, also Duke Mathematics Journal , vol. 1, pp. 328–55.Google Scholar
[56] Rosser, J. Barkley, Highlights of the history of the lambda-calculus, Annals of Historical Computing, vol. 6 (1984), no. 4, pp. 337–49.Google Scholar
[57] Shoenfield, Joseph R., Mathematical logic, Addison-Wesley, Reading, Massachusetts, 1967.Google Scholar
[58] Sieg, Wilfried, Mechanical procedures and mathematical experience, Mathematics and mind (George, A., editor), Oxford University Press, Oxford, 1994, pp. 71–117.Google Scholar
[59] Sieg, Wilfried, Aspects of mathematical experience, Philosophy of mathematics today (Agazzi, E. and Darvas, G., editors), Kluwer, 1996, pp. 195–217.Google Scholar
[60] Sieg, Wilfried and Byrnes, John, K-graph machines: generalizing Turing's machines and arguments, Gödel'96 (Hájek, Petr, editor), Lecture Notes in Logic, vol. 6, Springer-Verlag, 1996, pp. 98–119.Google Scholar
[61] Sieg, Wilfried and Byrnes, John, Gödel, Turing, and K-graph machines, to appear in Logic in Florence, 1997.Google Scholar
[62] Soare, Robert, Computability and recursion, this Bulletin, vol. 2 (1996), no. 3, pp. 284–321.Google Scholar
[63] Turing, Alan, On comptable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society. Series 2, vol. 42 (1936), pp. 230–265.Google Scholar