Potential Infinity and the Church Thesis

• Autorzy: Mostowski M.
• Języki publikacji: EN

Abstrakty

EN

In this paper we consider a "mathematical" proof of the Church Thesis. The proof is based on very weak assumptions about intuitive computability and the FM-representability theorem from [11]. It develops and improves the argument mentioned in [12]. Our argument essentially depends on the mathematical model of the world we are in.

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 81, nr 1-3
• Strony: 241--248
• Opis fizyczny: bibliogr. 20 poz.

Twórcy

autor

Mostowski M.

• Institute of Philosophy, Warsaw University, Krakowskie Przedmieście 3, 00-047 Warszawa, Poland,

Bibliografia

• [1] D. Hilbert, Gesammelte Abhandlungen. Springer-Verlag, 1935. available at: http://dz-srv1.sub.uni-goettingen.de/cache/toc/D41998.html
• [2] Aristotle. Physics. The Internet Classics Archive. available at: http://classic.mit.edu/Aristotle/physics.html
• [3] A. Church, An unsolvable problem of elementary theory. American Journal of Mathematics, 58:345-363, 1936.
• [4] R. Gandy, Church's thesis and principles for mechanism. In J. Barwise, H. J. Kiesler, and K. Kunen, editors, The Kleene Symposium, pages 123-148. North-Holland Publishing Company, 1980.
• [5] E. M. Gold, Limiting recursion. The Journal of Symbolic Logic, 30:28-48, 1965.
• [6] E. M. Gold, Language identification in the limit. Information and Control, 10:447-474, 1967.
• [7] D. Goldin and P.Wegner, The Church-Turing Thesis: Breaking the myth. In Löwe B., Torenvliet L., Cooper S. B., editors, Computations in Europe, LNCS 3526, pages 152-168. Springer-Verlag, 2005.
• [8] L. A. Kołodziejczyk, A finite-theoretical proof of a property of bounded query classes within PH. The Journal of Symbolic Logic, 69:1105-1116, 2004.
• [9] L. A. Kołodziejczyk, Truth definitions in finite models. The Journal of Symbolic Logic, 69:183-200, 2004.
• [10] M. Krynicki and K. Zdanowski, Theories of aritmetics in finite models. The Journal of Symbolic Logic, 70:0-28, 2005.
• [11] M. Mostowski, On representing concepts in finite models. Mathematical Logic Quarterly, 47:513-523, 2001.
• [12] M. Mostowski, On representing semantics in finite models. In Cachro J., Kurczewski G., Rojszczak A., editors, Philosophical dimensions of logic and science, pages 15-28. Kluwer Academic Publishers, 2003.
• [13] M.Mostowski and A.Wasilewska, Arithmetic of divisibility in finite models. Mathematical Logic Quarterly, 50:169-174, 2004.
• [14] M. Mostowski and D. Wojtyniak, Computational complexity of semantics of some natural language constructions. Annals of Pure and Applied Logic, 127:219-227, 2004.
• [15] M. Mostowski and K. Zdanowski, Coprimality in finite models. In L. Ong, editor, CSL 2005, LNCS 3634, pages 263-275. Springer-Verlag, 2005.
• [16] M.Mostowski and K. Zdanowski, FM-representability and beyond. In Löwe B., Torenvliet L., Cooper S. B., editors, Computations in Europe, LNCS 3526, pages 358-367. Springer-Verlag, 2005.
• [17] J. Mycielski, Analysis without actual infinity. The Journal of Symbolic Logic, 46:625-633, 1981.
• [18] P. Odifreddi, Classical Recursion Theory. North-Holland Publishing Company, 1989.
• [19] W. Sieg, Step by recursive step: Church's analysis of effective calculability. The Bulletin of Symbolic Logic, 3:154-180, 1997.
• [20] A. M. Turing, On computable numbers, with an application to the enscheidungsproblem. Proceedings London Mathematical Society, 42:230-265, 1936-7.