Proving as a Computable Procedure

• Autorzy: Calude C.S. , Rudeanu S.
• Języki publikacji: EN

Abstrakty

EN

Gödel's incompleteness theorem states that every finitely-presented, consistent, sound theory which is strong enough to include arithmetic is incomplete. In this paper we present elementary proofs for three axiomatic variants of Gödel's incompleteness theorem and we use them (a) to illustrate the idea that there is more than ``complete vs. incomplete", there are degrees of incompleteness, and (b) to discuss the implications of incompleteness and computer-assisted proofs for Hilbert's Programme. We argue that the impossibility of carrying out Hilbert's Programme is a thesis and has a similar status to the Church-Turing thesis.

Słowa kluczowe

EN

Hilbert programme; Gödel theorems; Church-Turing thesis; incompleteness

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2005
• Tom: Vol. 64, nr 1-4
• Strony: 43--52
• Opis fizyczny: bibliogr. 27 poz.

Twórcy

autor

Calude C.S.

• Department of Computer Science, The University of Auckland, Private Bag 92019, Auckland, New Zealand

autor

Rudeanu S.

• Faculty of Mathematics and Computer Science The University of Bucharest Str. Academiei 14, Bucharest, Romania

Bibliografia

• [1] G.S. Boolos, R.C. Jeffrey. Computability and Logic, Cambridge University Press, Cambridge, 1980. Second Edition.
• [2] C.S. Calude. Information and Randomness. An Algorithmic Perspective, Springer Verlag, Berlin, 1994. 2nd Edition, Revised and Extended, 2002.
• [3] C.S. Calude. Algorithmic Randomness, Quantum Physics, and Incompleteness, CDMTCS Research Report 248, 2004, 17 pp.
• [4] C.S. Calude, S. Marcus. Mathematical proofs at a crossroad? in J. Karhum¨aki, H. Maurer, G. Păun, G. Rozenberg (eds.). Theory Is Forever, Lectures Notes in Comput. Sci. 3113, Springer-Verlag, Berlin, 2004, 15–28.
• [5] G.J. Chaitin. Computers, paradoxes and the foundations of mathematics, American Scientist, 90March–April (2002), 164–171.
• [6] M. Davis, R. Sigal, E.J. Weyuker. Computability, Complexity, and Languages, Academic Press, New York, 1994. Second Edition.
• [7] M. Detlefsen. Hilbert’s Program: An Essay on Mathematical Instrumentalism, Reidel/Kluwer Academic, Dordrecht, 1986.
• [8] R.L. Epstein,W.A. Carnielli. Computability,Wadsworth & Brooks/Cole, Pacific Grove, California, 1989.
• [9] S. Feferman, J. Dawson, Jr., W. Goldfarb, C. Parsons, R.M. Solovay (eds.). Kurt Gödel Collected Works, Volume III, Oxford University Press, Oxford, 1995, 45–53.
• [10] S. Feferman, J. Dawson, Jr., W. Goldfarb, C. Parsons, W. Sieg (eds.). Kurt Gödel Collected Works, Volume V, Clarendon University Press, Oxford, 2003.
• [11] K. Gödel. The present situation in the foundations of mathematics (1930), in [9], 45–53.
• [12] K. Gödel. ¨Uber formal unentscheidbare S¨atze der Principia Mathematica und verwandter Systeme, Monatshefte f. Math. u. Phys. 38 (1931), 173–198.
• [13] K. Gödel. Lecture at Zilsel’s (1938), in [9], 87–113.
• [14] K. Gödel. Some basic theorems on the foundations of mathematics and their implications (1952), in [9], 304–335.
• [15] K. Gödel. The modern development of the foundations of mathematics in the light of philosophy (1961), in [9], 375–387.
• [16] K. Gödel. Letter to Leon Rappaport (1962), in [10], 176–177.
• [17] J. Herbrand. Sur la non-contradiction de l’Arithm´etique, J. Reine Angew. Math. 166 (1931), 1–8.
• [18] J. Hintikka. On Gödel,Wadsworth, Belmont, 2000.
• [19] S.C. Kleene. Introduction to Metamathematics, North-Holland, Amsterdam, 1952.
• [20] G. Kreisel, J. L. Krivine. Elements of Mathematical Logic, North-Holland, Amsterdam, 1967.
• [21] P. Odiffreddi. Classical Recursion Theory, North-Holland, Amsterdam, 1989.
• [22] H. Poincaré. Science et m´ethode, Flammarion, Paris, 1908. English translation by F. Maitland, with a preface by B. Russell, Nelson, London, 1914.
• [23] M. Presburger. ¨Uber die Vollst¨andigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt, Comptes Rendus du I Congr`es de Math´ematiciens des Pays Slaves,Warszawa, 1929, 92–101.
• [24] T. Skolem. Über einige Satzfunktionen in der Arithmetik, Skrifter utgitt av Det Norske Videnskaps-Akademi i Oslo, I. Matematisk naturvidenskapelig klasse, 7 (1931), 1–28.
• [25] S. G. Simpson (ed.). Reverse Mathematics 2001, http://www.math.psu.edu/simpson/revmath/ to appear.
• [26] C. Smoryński. The incompleteness theorems, in J. Barwise (ed.). Handbook of Mathematical Logic, North-Holland, Amsterdam, 1977, 821–866.
• [27] R.M. Solovay. A version of Ώ for which ZFC can not predict a single bit, in C.S. Calude, G. Păun (eds.). Finite Versus Infinite. Contributions to an Eternal Dilemma, Springer-Verlag, London, 2000, 323–334