Book contents
- Frontmatter
- Contents
- Turing's legacy: developments from Turing's ideas in logic
- Computability and analysis: the legacy of Alan Turing
- Alan Turing and the other theory of computation (expanded)
- Turing in Quantumland
- Computability theory, algorithmic randomness and Turing's anticipation
- Computable model theory
- Towards common-sense reasoning via conditional simulation: legacies of Turing in Artificial Intelligence
- Mathematics in the age of the Turing machine
- Turing and the development of computational complexity
- Turing machines to word problems
- Musings on Turing's Thesis
- Higher generalizations of the Turing Model
- Step by recursive step: Church's analysis of effective calculability
- Turing and the discovery of computability
- Transfinite machine models
- References
Step by recursive step: Church's analysis of effective calculability
Published online by Cambridge University Press: 05 June 2014
Edited by
Book contents
- Frontmatter
- Contents
- Turing's legacy: developments from Turing's ideas in logic
- Computability and analysis: the legacy of Alan Turing
- Alan Turing and the other theory of computation (expanded)
- Turing in Quantumland
- Computability theory, algorithmic randomness and Turing's anticipation
- Computable model theory
- Towards common-sense reasoning via conditional simulation: legacies of Turing in Artificial Intelligence
- Mathematics in the age of the Turing machine
- Turing and the development of computational complexity
- Turing machines to word problems
- Musings on Turing's Thesis
- Higher generalizations of the Turing Model
- Step by recursive step: Church's analysis of effective calculability
- Turing and the discovery of computability
- Transfinite machine models
- References
Summary
In fact, the only evidence for the freedom from contradiction of Principia Mathematica is the empirical evidence arising from the fact that the system has been in use for some time, many of its consequences have been drawn, and no one has found a contradiction.
(Church in a letter to Godel, July 27, 1932)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.
- Type
- Chapter
- Information
- Turing's LegacyDevelopments from Turing's Ideas in Logic, pp. 434 - 466Publisher: Cambridge University PressPrint publication year: 2014
References
1935–1936 Logical Calculus; Notes by Prof. Bernays with assistance of Mr. F.A. Ficken, The Institute for Advanced Studies, Princeton, 125 pp.
1927 Alternatives to Zermelo's assumption; Transactions of the American Mathematical Society, vol. 29, pp. 178-208. (Ph.D. thesis; Princeton.)
1928 On the law of the excluded middle; American Mathematical Society. Bulletin, vol. 34, pp. 75-781.Google Scholar
1932 A set of postulates for the foundation of logic, part I; Annals of Mathematics, vol. 33, pp. 346-366.Google Scholar
1933 A set of postulates for the foundation of logic, part II; Annals of Mathematics, vol. 34, pp. 839-864.Google Scholar
1935 A proof of freedom from contradiction; Proceedings of the National Academy of Sciences of the United States of America, vol. 21, pp. 275-81; reviewed in (Gödel 1936b).Google Scholar
1935a An unsolvable problem of elementary number theory; American Mathematical Society. Bulletin, vol. 41, pp. 332-333.Google Scholar
1936 An unsolvable problem of elementary number theory; American Journal of Mathematics, vol. 58, pp. 345-363.Google Scholar
1936a A note on the Entscheidungsproblem; The Journal of Symbolic Logic, vol. 1, pp. 40-41, and Corrections, Church Alonzo 1936a A note on the Entscheidungsproblem; The Journal of Symbolic Logic, vol. 1, pp. 101–102.Google Scholar
1956 Introduction to mathematical logic, volume I; Princeton University Press, Princeton.
and 1935 Some properties of conversion; American Mathematical Society. Bulletin, vol. 41, p. 332.Google Scholar
and 1936 Some properties of conversion; Transactions of the American Mathematical Society, vol. 39, pp. 472-482.
and 1935 Formal definitions in the theory of ordinal numbers; American Mathematical Society. Bulletin, vol. 41, p. 627.Google Scholar
and 1936 Formal definitions in the theory of ordinal numbers; Fundamenta Mathematicae, vol. 28, pp. 11-21.Google Scholar
*1958 Computability and unsolvability; McGraw-Hill.
1965 The Undecidable; Raven Press, Hewlett, New York.
1982 Why Gödel didn't have Church's Thesis; Information and Control, vol. 54, pp. 3-24.Google Scholar
*1994 Emil L. Post: His life and his work; in Solvability, Provability, Definability: The Collected Works of Emil L. Post, (, editor), Birkhäuser, pp. xi–xxviii.
1995 American logic in the 1920s; The Bulletin of Symbolic Logic, vol. 1, pp. 273-278.Google Scholar
1997 Logical Dilemmas—The life and work of Kurt Gödel; A. K. Peters, Wellesley.
1872 Stetigkeit und irrationale Zahlen; Vieweg, Braunschweig.
1888 Was sind und was sollen die Zahlen?; Vieweg, Braunschweig.
1988 Turing in the land of O(z); in The Universal Turing Machine (, editor), Oxford University Press, Oxford, 1988, pp. 113-147.
1988 The confluence of ideas; in The Universal Turing Machine, (, editor), Oxford University Press, Oxford, 1988, pp. 55-111.
1931 On formally undecidable propositions of Principia Mathematica and related systems I; in Collected Works I, pp. 145-195.
1933o The present situation in the foundations of mathematics; in Collected Works III, pp. 45-53.
1934 On undecidable propositions offormal mathematical systems; in Collected Works I, pp. 346-371.
1934e Review of Church 1933; in Collected Works I, pp. 381-383.
1936a On the length of proofs; in Collected Works I, pp. 397-399.
1936b Review of Church 1935; in Collected Works I, pp. 399-401.
*193? [[Undecidable Diophantine propositions]]; in Collected Works III, pp. 164-175.
1946 Remarks before the Princeton bicentennial conference on problems in mathematics; in Collected Works II, pp. 150-153.
1986 Collected Works I, Oxford University Press, Oxford.
1990 Collected Works II, Oxford University Press, Oxford.
1995 Collected Works III, Oxford University Press, Oxford.
*2003a Collected Works VI, Oxford University Press, Oxford.
*2003b Collected Works V, Oxford University Press, Oxford.
1919 Natur und mathematisches Erkennen; Lecture given in the Winter term 1919, the notes were written by ; reprint by the Mathematical Institute of the University Göttingen, 1989.
and 1934 Grundlagen der Mathematik I, Springer Verlag, Berlin.
and 1939 Grundlagen der Mathematik II, Springer Verlag, Berlin.
1935 A theory ofpositive integers in formal logic; American Journal of Mathematics, vol. 57, pp. 153–173 and 219-244.Google Scholar
1935a General recursive functions of natural numbers; American Mathematical Society. Bulletin, vol. 41, p. 489.Google Scholar
1935b λ-definability and recursiveness; American Mathematical Society. Bulletin, vol. 41, p. 490.Google Scholar
1936 General recursive functions of natural numbers; Mathematische Annalen, vol. 112, 727-742.Google Scholar
1936a λ-definability and recursiveness; Duke Mathematical Journal, vol. 2, pp. 340-353. (1935a and b are abstracts of these two papers and were received by the AMS on July 1, 1935.)Google Scholar
1936b A note on recursive functions; American Mathematical Society. Bulletin, vol. 42, pp. 544-546.Google Scholar
1952 Introduction to metamathematics; Wolters-Noordhoff Publishing, Groningen.
1981 Origins of recursive function theory; Annals of the History of Computing, vol. 3, pp. 52-66.Google Scholar
and 1935 The inconsistency of certain formal logics; American Mathematical Society. Bulletin, vol. 41, p. 24.Google Scholar
and 1935 The inconsistency of certain formal logics; Annals of Mathematics, vol. 36, no. 2, pp. 630-636.Google Scholar
1990 Second thoughts about Church's Thesis and mathematical proofs; The Journal of Philosophy, vol. 87, no. 5, 225-233.Google Scholar
1996 Kreisel's Church; in Kreiseliana (, editor), A. K. Peters, Wellesley, pp. 389-415.
1938 Ein Verfahren der mathematischen Logik; The Journal of Symbolic Logic, vol. 3, pp. 61-76.Google Scholar
1936 Finite combinatory processes. Formulation I; The Journal of Symbolic Logic, vol. 1, pp. 103-105.Google Scholar
*1941 Absolutely unsolvable problems and relatively undecidable propositions—Account of an anticipation; submitted to the American Journal of Mathematics in 1941, but published only in Davis' “The Undecidable” in 1965. (The mathematical core was published in (Post 1943).)Google Scholar
*1943 Formal reductions of the general combinatorial decision problem; American Journal of Mathematics, vol. 55, no. 2, pp. 197-215.Google Scholar
*1947 Recursive unsolvability of a problem of Thue; The Journal of Symbolic Logic, vol. 12, pp. 1-11.Google Scholar
1935 A mathematical logic without variables; Annals of Mathematics, vol. 36, no. 2, pp. 127-150 and Duke Mathematical Journal, vol. 1, pp. 328–355.Google Scholar
1984 Highlights of the history of the lambda-calculus; Annals of the History of Computing, vol. 6, no. 4, pp. 337-349.Google Scholar
*2006 Gödel on Turing on computability; in Church's Thesis after 70 years, (, and , editors), Ontos Verlag, pp. 393-419.
1967 Mathematical Logic; Addison-Wesley, Reading (Massachusetts).
1994 Mechanical procedures and mathematical experience; in Mathematics and Mind, (, editor), Oxford University Press, Oxford, pp. 71-117.
1996 Aspects of mathematical experience; in Philosophy of Mathematics Today, ( and , editors), Kluwer, pp. 195-217.
*2002 Calculations by man and machine: conceptual analysis; in Reflections on the Foundations of Mathematics (, and , editors), Lecture Notes in Logic 15, Association for Symbolic Logic, pp. 390-409.
*2005 Only two letters: The correspondence between Herbrand and Gödel; The Bulletin of Symbolic Logic, vol. 11, no. 2, pp. 172-184.Google Scholar
and 1996 K-graph machines: generalizing Turing's machines and arguments; in Gödel '96, (, editor), Lecture Notes in Logic 6, Springer Verlag, pp. 98-119.
and 1997 Gödel, Turing, and K-graph machines; in Logic and Foundations of Mathematics, ( et al. editors), Kluwer Academic Publisher, pp. 57-66.
1996 Computability and recursion; The Bulletin of Symbolic Logic, vol. 2, pp. 284-321.Google Scholar
1936 On computable numbers, with an application to the Entscheidungsproblem; Proceedings of the London Mathematical Society, Second Series, vol. 42, pp. 230-265.Google Scholar
*1950 The word problem in semi-groups with cancellation; Annals of Mathematics, vol. 52, pp. 491-505.Google Scholar