The progress of science from a computational point of view: the drive towards ever higher solvability

• Autorzy: Marciszewski Witold

Identyfikatory

DOI

10.2478/fcds-2019-0002

• Języki publikacji: EN

Abstrakty

EN

This essay's content is rendered by the titles of the successive sections. 1. Effective solvability versus intuitive solvability. — 2. Decidability, i.e. effective solvability, in predicate logic. The speedup phenomenon — 3. Contributions of the second-order logic to the problems of solvability — 4. The infinite progress of science in the light of Turing's idea of the oracle. The term "oracle" is a technical counterpart of the notion of mathematical intuition. A more detailed summary can be obtained through juxtaposing the textboxes labelled with letters A...F. Conclusion: in the progress of science an essential role is played by the feedback between intellectual intuitions (intuitive solvability) and algorithmic procedures (effective solvability).

Słowa kluczowe

EN

effective solvability; intuitive solvability; decidability; speed up; second-order logic; solvability; oracle; mathematical intuition; progress of science; algorithmic procedure

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2019
• Tom: Vol. 44, No. 1
• Strony: 11--26
• Opis fizyczny: Bibliogr. 29 poz.

Twórcy

autor

Marciszewski Witold

Bibliografia

• [1] Benzmüller Ch., Kerber M., A Challenge for Mechanized Deduction (to find the full text in Web ask Google for the title and select the relevant PDF), 2001.
• [2] Benzmüeller Ch., Brown Ch., The Curious Inference of Boolos in Mizar and OMEGA in: Studies in Logic Grammar and Rhetoric (http://logika.uwb.edu.pl/studies/index.php?page=search&vol=23) 23, 2007.
• [3] Boolos G., A Curious Inference? Journal of Philosophical Logic, 16, 1987, 1-12.
• [4] Buss S.R., On Godel’s Theorems on Lengths of Proofs I: Number of Lines and Speedup for Arithmetics, J. Symbolic Logic, 59, 3, 1994, 737-756.
• [5] Fischer M.J., Rabin M.O., Super-Exponential Complexity of Presburger Arithmetic, Proceedings of the SIAM-AMS Symposium in Applied Mathematics, 7, 1974, 27-41.
• [6] Fraenkel A.A., Abstract Set Theory North Holland, 1976.
• [7] Gödel K., Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I, Monatshefte für Mathematik und Physik, 38, 1931, 173-198.
• [8] Gödel K., Über die Lange von Beweisen Ergeb. Math. Kolloquiums, 7, 1936, 23-24.
• [9] Gödel K., Kurt Gödel Collected Works, vol. 1. Oxford Univ. Press, Oxford, 1986.
• [10] Hartmanis J., Stearns R., On the computational complexity of algorithms, Transactions of the AMS, 117, 1965, 285-306.
• [11] Hilbert D., Ackermann W., Grundzüge der theoretischen Logik, Springer, 1928.
• [12] Hilbert D., Naturerkennen und Logik, Naturwissenschaften, Heft 47/48/49, 28.II.1930 959-963.
• [13] Hilbert D., Bernays P., Grundlagen der Mathematik Springer (vol. 1), 1934, (vol. 2), 1939.
• [14] Kneale W., Kneale M., The Development of Logic Clarendon Press, 1962.
• [15] Kuhn T., The Structure of Scientific Revolutions University of Chicago Press 1962, rev. ed. 1970.
• [16] Marciszewski W. (ed.), Dictionary of Logic as Applied in the Study of Language. Concepts, Methods, Theories, Nijhoff, 1981.
• [17] Marciszewski W., Murawski R., Mechanization of Reasoning in a Historical Perspective, Rodopi, 1995.
• [18] Marciszewski W., Hypercomputational vs. computational complexity. A challenge for methodology of the social sciences in: Free Market and Computational Complexity. Essays in Commemoration of Friedrich Hayek (1899-1992) of the series Studies in Logic, Grammar and Rhetoric (http://logika.uwb.edu.pl/studies/index.php?page=search&vol=18) 5(18), 2002.
• [19] Marciszewski W., The Gödelian Speed-up and Other Strategies to Address Decidability and Tractability Studies in Logic Grammar and Rhetoric, 9(22), 2006.
• [20] Newman M.H.A., Alan Mathison Turing, Biographical memoirs of the Royal Society, 1955, 253-263.
• [21] Placek T., Mathematical Intuitionism and Intersubjectivity: A Critical Exposition of Arguments for Intuitionism Springer Science & Business Media, 1999.
• [22] Poincaré H., The Value of Science (French La Valeur de la Science, 1905) Dover Publications, 1958.
• [23] Surma S.J., Deduction theorem in: Marciszewski (ed.) Dictionary of Logic as Applied in the Study of Language. Concepts, Methods, Theories, Nijhoff, 1981, 77-81.
• [24] Tarski A., Logic, Semantics, Metamathematics, translated by J.H. Woodger, Clarendon Press, 1956.
• [25] Tarski A., On some fundamental concepts of metamathematics in: Tarski A., Logic, Semantics, Metamathematics, 1956, German original published in the proceedings of the Scientific Society of Warsaw, 1930.
• [26] Turing A., On computable numbers with an application to the Entscheidungsproblem, Proc. of the London Math. Society, Series 2, 1936, 230-265.
• [27] Turing A., Systems of logic defined by ordinals, Proc. Lond. Math. Soc. Ser. 2, 45, 1939, 161-228.
• [28] Webb J.C., Mechanism, Mentalism, and Metamathematics, Reidel, 1980.
• [29] Wittgensten L., Tractatus Logico-Philosophicus, Routledge & Kegan Paul, 1921.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).