Abstract
DOI: http://doi.org/10.26333/sts.xxxiv1.03
The incompleteness theorems constitute the mathematical core of Gödel’s philosophical challenge. They are given in their “most satisfactory form”, as Gödel saw it, when the formality of theories to which they apply is characterized via Turing machines. These machines codify human mechanical procedures that can be carried out without appealing to higher cognitive capacities. The question naturally arises, whether the theorems justify the claim that the human mind has mathematical abilities that are not shared by any machine. Turing admits that non-mechanical steps of intuition are needed to transcend particular formal theories. Thus, there is a substantive point in comparing Turing’s views with Gödel’s that is expressed by the assertion, “The human mind infinitely surpasses any finite machine”. The parallelisms and tensions between their views are taken as an inspiration for beginning to explore, computationally, the capacities of the human mathematical mind.
References
Abramson, D. (2008). Turing’s Responses to Two Objections. Minds & Machines, 18(2), 147–167.
Ackermann, W. (1924). Begründung des ‘tertium non datur’ mittels der Hilbertschen Theorie der Widerspruchsfreiheit. Mathematische Annalen, 93, 1–36.
Church, A. (1935). An Unsolvable Problem of Elementary Number Theory. Bulletin of the AMS, 41, 332–333.
Copeland, J. (2004). The Essential Turing: The Ideas That Gave Birth to the Computer Age. Oxford: Clarendon Press.
Copeland, J. (2006). Turing’s Thesis. In: A. Olszewski, J. Wolenski, R. Janusz (Eds.), Church’s Thesis After 70 Years (pp. 147–174). Frankfurt: Ontos Verlag.
Davis, M. (1982). Why Gödel Did Not Have Church’s Thesis. Information and Control, 54, 3–24.
Dawson, John W. (2006). Gödel and the Origin of Computer Science. Lecture at CiE 2006, Swansea.
Dedekind, R. (1888). Was sind und was sollen die Zahlen? Braunschweig: Vieweg.
Feferman, S. (1988). Turing in the Land of O(z). In: R. Herken (Ed.), The Universal Turing Machine—A Half-Century Survey (pp. 113–147). Oxford: Oxford University Press.
Feferman, S. (2006a). Are There Absolutely Unsolvable Problems? Gödel’s Dichotomy. Philosophia Mathematica, 14(2), 134–152.
Feferman, S. (2006b). Turing’s Thesis. Notices of the AMS, 53(10), 1200–1205.
Gandy, R. (1980). Church’s Thesis and Principles for Mechanisms. In: J. Barwise, H. J. Keisler, K. Kunen (Eds.), The Kleene Symposium (pp. 123–148), Amsterdam: North-Holland Publishing Company.
Gödel, K. (1931). Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I [On Formally Undecidable Propositions of Principia Mathematica and Related Systems I]. Monatshefte für Mathematik und Physik, 38, 173–198.
Gödel, K. (1933). The Present Situation in the Foundations of Mathematics. In: K. Gödel, Collected Works III (pp. 45–53). Oxford: Oxford University Press.
Gödel, K. (1934). On Undecidable Propositions of Formal Mathematical Systems. In: K. Gödel, Collected Works I (pp. 346–371). Oxford: Oxford University Press.
Gödel, K. (1936). Über die Länge von Beweisen. Ergebnisse eines mathematischen Kolloquiums, Heft 7, 23–24.
Gödel, K. (1939). Finding Aid (Notre Dame Lecture on Logic, Spring 1939). In: K. Gödel, Collected Works IV–V (pp. 527–528). Oxford: Oxford University Press.
Gödel, K. (193?). Undecidable Diophantine Propositions. In: K. Gödel, Collected Works III (pp. 164–175). Oxford: Oxford University Press.
Gödel, K. (1946). Remarks Before the Princeton Bicentennial Conference on Problems in Mathematics. In: K. Gödel, Collected Works II (pp. 150–153). Oxford: Oxford University Press.
Gödel, K. (1947). What is Cantor’s Continuum Problem? In: K. Gödel, Collected Works II (pp. 167–187). Oxford: Oxford University Press.
Gödel, K. (1951). Some Basic Theorems on the Foundations of Mathematics and Their Implications. In: K. Gödel, Collected Works III (pp. 304–323). Oxford: Oxford University Press.
Gödel, K. (1964). Postscriptum for [1934]. In: K. Gödel, Collected Works I (pp. 369–371). Oxford: Oxford University Press.
Gödel, K. (1972). Some Remarks on the Undecidability Results. In: K. Gödel, Collected Works II (pp. 305–306). Oxford: Oxford University Press.
Gödel, K. (1974). Note. In: H. Wang, From Mathematics to Philosophy (pp. 325–326). London: Routledge & Kegan Paul.
Gödel, K. (1986). Collected Works I. Oxford: Oxford University Press.
Gödel, K. (1990). Collected Works II. Oxford: Oxford University Press.
Gödel, K. (1995). Collected Works III. Oxford: Oxford University Press.
Gödel, K. (2003). Collected Works IV–V. Oxford: Oxford University Press.
Herbrand, J. (1931). On the Consistency of Arithmetic. In: W. Goldfarb (Ed.), Jacques Herbrand, Logical Writings (pp. 282–298). Cambridge, Mass.: Harvard University Press.
Herken, R. (Ed.). (1988). The Universal Turing Machine—A Half-Century Survey. Oxford: Oxford University Press.
Hilbert, D. (1900). Über den Zahlbegriff. Jahresbericht der Deutschen Mathematiker Vereinigung, 8, 180–194.
Hilbert, D. (1905). Über die Grundlagen der Logik und der Arithmetik. In: A. Krazer (Ed.), Verhandlungen des 3. Internationalen Mathematiker-Kongresses: in Heidelberg vom 8. bis 13 (pp. 174–185). Leipzig: Teubner.
Hilbert, D. (1923). Die logischen Grundlagen der Mathematik. Mathematische Annalen, 88, 151–165.
Hilbert, D., Bernays, P. (1921/2). Grundlagen der Mathematik. in: W. Ewald, W. Sieg (Eds.), David Hilbert’s Lectures on the Foundations of Arithmetic and Logic 1917–1933 (pp. 431–521). Springer.
Hilbert, D., Bernays, P. (1934). Grundlagen der Mathematik I. Berlin: Springer Verlag.
Hilbert, D., Bernays, P. (1939). Grundlagen der Mathematik II. Berlin: Springer Verlag.
Kennedy, J., van Atten, M. (2004). Gödel’s Modernism: On Set-Theoretic Incompleteness. Graduate Faculty Philosophy Journal, 25(2), 289–349.
Kennedy, J., van Atten, M. (2009). “Gödel’s Modernism: On Set-Theoretic Incompleteness”, Revisited. In: S. Lindström et al. (Eds.), Logicism, Intuitionism, and Formalism—What Has Become of Them? (Synthese Library 341, pp. 303–355). Springer.
Kolmogorov, A., Uspenski, V. (1963). On the Definition of an Algorithm. AMS Translations, 21(2), 217–245.
Martin, D. A. (2005). Gödel’s Conceptual Realism. Bulletin of Symbolic Logic, 11(2), 207–224.
Post, E. (1947). Recursive Unsolvability of a Problem of Thue. J. Symbolic Logic, 12, 1–11.
Sieg, W. (1994). Mechanical Procedures and Mathematical Experience. In: A. George (Ed.), Mathematics and Mind (pp. 71–117). Oxford: Oxford University Press.
Sieg, W. (1997). Step by Recursive Step: Church’s Analysis of Effective Calculability. Bulletin of Symbolic Logic, 3(2), 154–180.
Sieg, W. (1999). Hilbert’s Programs: 1917–1922. Bulletin of Symbolic Logic, 11(2), 1–44.
Sieg, W. (2002). Calculations by Man and Machine: Conceptual Analysis. In: W. Sieg, R. Sommer, C. Talcott (Eds.), Reflections on the Foundations of Mathematics (Lecture Notes in Logic 15, pp. 390–409). Cambridge University Press.
Sieg, W. (2006). Gödel on Computability. Philosophia Mathematica, 14(2), 189–207.
Sieg, W. (2007). On Mind & Turing’s Machines. Natural Computing, 6, 187–205.
Sieg, W. (2009a). On Computability. In: A. D. Irvine (Ed.), Philosophy of Mathematics (pp. 535–630). Amsterdam: North Holland.
Sieg, W. (2009b). Hilbert’s Proof Theory. In: D. M. Gabbay, J. Woods (Eds.), Handbook of the History of Logic. Volume 5: Logic from Russell to Church (pp. 321–384). Amsterdam: North Holland.
Sieg, W. (2010). Searching for Proofs (And Uncovering Capacities of the Mathematical Mind). In: S. Feferman, W. Sieg (Eds.), Proofs, Categories and Computations (pp. 189–215). London: College Publications.
Sieg, W., Byrnes, J. (1996). K-Graph Machines: Generalizing Turing’s Machines and Arguments. In: P. Hájek (Ed.), Godel ‘96: Logical Foundations of Mathematics, Computer Science and Physics (Lecture Notes in Logic 6, pp. 98–119). Berlin: Springer Verlag.
Sieg, W., and D. Schlimm (2005). Dedekind’s Analysis of Number: Systems and Axioms. Synthese, 147, 121–170.
Stein, H. (1988). Logos, Logic, and Logistiké: Some Philosophical Remarks on Nineteenth-Century Transformation of Mathematics. In: W. Aspray, P. Kitcher (Eds.), History and Philosophy of Modern Mathematics (vol. XI of Minnesota Studies in the Philosophy of Science, pp. 238–259). Minneapolis: University of Minnesota Press.
Turing, A. M. (1936). On Computable Numbers, With an Application to the Entscheidungsproblem. Proc. London Math. Soc. (series 2), 42, 230–265.
Turing, A. M. (1939). Systems of Logic Based on Ordinals. Proc. London Math. Soc. (series 2), 45, 161–228.
Turing, A. M. (1947). Lecture to the London Mathematical Society on 20 February 1947. In: D. C. Ince (Ed.), Collected Works of A.M. Turing—Mechanical Intelligence (87–105). Amsterdam: North Holland.
Turing, A. M. (1948). Intelligent Machinery. In: D. C. Ince (Ed.), Collected Works of A.M. Turing—Mechanical Intelligence (107–127). Amsterdam: North Holland.
Turing, A. M. (1950). Computing Machinery and Intelligence. Mind, 59, 433–460.
Turing, A. M. (1951a). Intelligent Machinery, A Heretical Theory [Radio broadcast]. Printed in J. Copeland, The Essential Turing: The Ideas That Gave Birth to the Computer Age (pp. 472–475). Oxford: Clarendon Press.
Turing, A. M. (1951b). Can Digital Computers Think? [Radio broadcast]. Printed in J. Copeland, The Essential Turing: The Ideas That Gave Birth to the Computer Age (pp. 482–486). Oxford: Clarendon Press.
Turing, A. M. (1952). Can Automatic Calculating Machines Be Said to Think? [Radio discussion of A. Turing, R. Braithwaite, G. Jefferson, and M. Newman. Printed in J. Copeland, The Essential Turing: The Ideas That Gave Birth to the Computer Age (pp. 494–506). Oxford: Clarendon Press.
Turing, A. M. (1954). Solvable and Unsolvable Problems. Science News, 31, 7–23.
van Heijenoort, J. (1968). From Frege to Gödel—A Source Book in Mathematical Logic, 1879–1931. Cambridge, Mass.: Harvard University Press.
Wang, H. (1974). From Mathematics to Philosophy. London: Routledge & Kegan Paul.
NEW REFERENCES (FOR THE POSTSCIPTUM)
Bernays, P. (1930). Die Philosophie der Mathematik und die Hilbertsche Beweistheorie. In: P. Bernays, Abhandlungen zur Philosophie der Mathematik (pp. 17–61). Darmstadt: Wissenschaftliche Buchgesellschaft.
Davis, M., Sieg, W. (2015). Conceptual Confluence in 1936: Post and Turing. In: G. Sommaruga, T. Strahm (Eds.), Turing’s Revolution (pp. 3–27). Berlin: Springer.
Gentzen, G. (1936). Die Widerspruchsfreiheit der reinen Zahlentheorie. Mathematische Annalen, 112(1), 493–565.
Hilbert, D. (1918). Axiomatisches Denken. Mathematische Annalen, 78, 405–415.
Hilbert, D., Ackermann, W. (1928). Grundzüge der theoretischen Logik. Berlin: Springer.
Hilbert, D., Bernays, P. (1917–18). Prinzipien der Mathematik. In: W. Ewald, W. Sieg (Eds.), David Hilbert’s Lectures on the Foundations of Arithmetic and Logic 1917–1933 (pp. 59–221). Berlin: Springer.
Sieg, W. (2013). Hilbert’s Programs and Beyond. Oxford: Oxford University Press.
Sieg, W. (2014). The Ways of Hilbert’s Axiomatics: Structural and Formal. Perspectives on Science, 22(1), 133–157.
Sieg, W. (2018). What is the Concept of Computation? In: F. Manea, R.G. Miller, D. Nowotka (Eds.), Sailing Routes in the World of Computation, Proceedings of CiE 2018 (pp. 386–396). Springer LNCS 10936.
Sieg, W., Morris, R. (2018). Dedekind’s Structuralism: Creating Concepts and Deriving Theorems. In: E. H. Reck (Ed.), Logic, Philosophy of Mathematics, and Their History: Essays in Honor of W.W. Tait (pp. 251–301). London: College Publications.
Sieg, W., Walsh, P. (2019). Natural Formalization: Deriving the Cantor-Bernstein Theorem in ZF. The Review of Symbolic Logic. doi:10.1017/S175502031900056X
Sieg, W., Derakhshan, F. (2020). Human-Centered Automated Proof Search. Manuscript submitted for publication.
Sieg, W., Szabo, M., McLaughlin, D. (2016). Why Post Did [Not] Have Turing’s Thesis. In: E. Omodeo, A. Policriti (Eds.), Martin Davis on Computability, Computational Logic, and Mathematical Foundations (pp. 175–208). Berlin: Springer.