Abstract
In the paper some applications of Gödel's incompleteness theorems to discussions of problems of computer science are presented. In particular the problem of relations between the mind and machine (arguments by J.J.C. Smart and J.R. Lucas) is discussed. Next Gödel's opinion on this issue is studied. Finally some interpretations of Gödel's incompleteness theorems from the point of view of the information theory are presented.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Benacerraf, P. (1967), ‘God, the Devil, and Gödel’, The Monist, 51, 9–32.
Bowie, G.L. (1982), ‘Lucas' Number Is Finally Up’, Journal of Philosophical Logic, 11, 279–285.
Chaitin, G. (1974), ‘Information—Theoretic Computational Complexity’, IEEE Transactions on Information Theory, IT-20, 10–15. Reprinted in: Tymoczko, T. (ed.), New Directions in the Philosophy of Mathematics. An Anthology, Boston-Basel-Stuttgart: Birkhäuser, 289–299.
Chaitin, G. (1982), Gödel's Theorem and Information, International Journal of Theoretical Physics, 21, 941–954 Reprinted in: Tymoczko, T. (ed.), New Directions in the Philosophy of Mathematics. An Anthology, Boston-Basel-Stuttgart: Birkhäuser, 300–311.
Davis, M. (ed.) (1965), The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems, and Computable Functions, Hewlett, N.Y.: Raven Press.
Descartes R. (1637), Discours de la méthode pour bien conduire sa raison et chercher la vérité dans les sciences. Reprinted in: Oeuvres complètes, ed. by Adam, Ch. and Tannery, P., Paris 1897–1913, second edition: Paris 1956–1957.
Gödel, K. (1931), ‘Über formal unentscheidbare Sätze der ‘Principia Mathematica’ und verwandter Systeme.’ I, Monatshefte für Mathematik und Physik, 38, 173–198. Reprinted with English translation: ‘On Formally Undecidable Propositions of Principia Mathematica and Related Systems’, in: Gödel, K., Collected Works, vol. I, ed. by Feferman, S. et al., Oxford: Oxford University Press, New York and Clarendon Press, 144–195.
Gödel, K. (1944), ‘Russell's Mathematical Logic’, in: Schilpp, P.A. (ed.), The Philosophy of Bertrand Russell, Evanston: Northwestern University, 123–153. Reprinted in: Gödel, K., Collected Works, vol. II, ed. by Feferman, S. et al., Oxford: Oxford University Press, New York and Clarendon Press, 119–141.
Gödel, K. (1951), ‘Some Basic Theorems on the Foundations of Mathematics and Their Implications’, first published in: Gödel, K., Collected Works, vol. III, ed. by Feferman, S. et al., Oxford: Oxford University Press, New York and Clarendon Press, 304–323.
Good, I.J. (1967), ‘Human and Machine Logic’, British Journal for the Philosophy of Science, 18, 145–146.
Good, I.J. (1969), ‘Gödel's Theorem is a Red Herring’, British Journal for the Philosophy of Science, 19, 357–358.
Hilbert, D. (1926), ‘Über das Unendliche’, Mathematische Annalen, 95, 161–190. English translation: On the Infinite, in: Heijenoort, J. van (eds.) (1967), From Frege to Gödel. A Source Book in Mathematical Logic, 1879–1931, Cambridge, Mass.: Harvard University Press, 367–392.
Hofstadter, D.R. (1979), Gödel, Escher, Bach: An Eternal Golden Briad, New York; Basic Books.
Krajewski, S. (1983), ‘Philosophical Conscqucnces of Gödel's Theorems’, Dulletin of the Section of Logic, 12, 157–164.
Krajewski, S. (1993), ‘Did Gödel Prove That we Are Not Machines?’, in: Wolkowski, Z.W. (ed.), First International Symposium on Gödel's Theorems, Singapore-New Jersey-Lon-don-Hong Kong: World Scientific, 39–49.
Kreisel, G. (1980), ‘Kurt Gödel 1906–1978’, Biographical Memoires of Fellows of the Royal Society, 26, 149–224.
La Mettrie, J.O. de (1748), L'homme-machine. Critical edition, ed. by A. Vartanian, Paris 1960.
Lucas, J.R. (1961), ‘Minds, Machines and Gödel’, Philosophy, 36, 112–127. Reprinted in: Anderson, A.R. (ed.), (1964), Minds and Machines, Prentice Hall: Englewood Cliffs.
Lucas, J.R. (1967), ‘Human and Machine Logic. A Rejoinder’, British Journal for the Philosophy of Science, 19, 155–156.
Lucas, J.R. (1968), ‘Satan Stultified: A Rejoinder to Paul Benacerraf’, The Monist, 52, 145–158.
Mendelson, E. (1964), Introduction to Mathematical Logic, Princeton-Toronto-New York-London: D. Van Nostrand Company, Inc.
Murawski, R. (199?), Recursive Functions and Metamathematics, to appear.
Nagel, E. and Newman, J.R. (1958), Gödel's Proof, London: Routledge & Kegan Paul, Ltd.
Penrose, R. (1989), The Emperor's New Mind. Concerning Computers, Minds, and the Laws of Physics, Oxford: Oxford University Press.
Penrose, R. (1994), Shadows of the Mind: a Search for the Missing Science of Consciousness, Oxford-New York-Melbourne: Oxford University Press.
Putnam, H. (1975), ‘What Is Mathematical Truth?’, in: Putnam, H. Mathematics, Matter and Method. Philosophical Papers, vol. I, Cambridge-London-New York-Melbourne: Cambridge University Press, 60–78. Reprinted in: Tymoczko, T. (ed.), New Directions in the Philosophy of Mathematics. An Anthology, Boston-Basel-Stuttgart: Birkhäuser, 50–65.
Rucker, R. (1982), Infinity and the Mind, Boston-Basel-Stuttgart: Birkhäuser.
Smart, J.J.C. (1961), ‘Gödel's Theorem, Church's Thesis, and Mcchanism’, Synthese, 13, 105–110.
Smoryński, C. (1977), ‘The Incompleteness Theorems’, in: Barwise, J. (ed.), Handbook of Mathematical Logic, Amsterdam, North-Holland Publ. Comp, 821–865.
Turing A. (1950), ‘Computing Machinery and Intelligence’, Mind, 59, 433–460. Reprinted in:, Anderson, A.R. (ed.), (1964), Minds and Machines, Prentice Hall: Englewood Cliffs, 4–42.
Wang Hao, (1974), From Mathematics to Philosophy, London: Routledge and Kegan Paul.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Murawski, R. Gödel's Incompleteness Theorems and Computer Science. Foundations of Science 2, 123–135 (1997). https://doi.org/10.1023/A:1009639629935
Issue Date:
DOI: https://doi.org/10.1023/A:1009639629935