From decidability to feasibility Duccio Pianigiani University of Siena, Italy This is a section of Lectures in Proof Theory and Complexity(DOI: 10.36253/979-12-215-0778-2) by Duccio Pianigiani Firenze University Press, USiena Press Florence 2025 https://doi.org/10.36253/979-12-215-0778-2.04

Available for academic research purposes

Open Access

Copyright Author(s)

Content licence CC BY-SA 4.0

Metadata licence CC0 1.0

This is original content, published for academic research purposes

 Digital edition XML powered by Booksflow

We focus on some classical results concerning formal arithmetic,dating back to the classical era of the 1930s and 1940s, then in subsequent chapters inviting a comparison with more recent results. In this regard, we strongly emphasise the acceleration imparted also to logical study by the development of computer science: in addition to decidability in principle, indeed, computer science has forced attention to be paid to the classification of mathematical problems according to their degree of difficulty and the computational means that can be used in practice.

 Entscheidungsproblem Turing’s Halting Problem decidability polynomial-time computability Cook-Levin Theorem

It is available online at https://doi.org/10.36253/979-12-215-0778-2.04

References Ausiello, Giorgio and Gambosi, Giorgio and d’Amore, Fabrizio. 2002. Linguaggi, Modelli, Complessità. Milano: Franco Angeli. Bernays, Paul. Letter to Gödel, 7 January 1970. Bernays Papers, ETH Zürich Library/WHS, Hs. 975:1745. Buss, Samuel R. 1995. “On Gödel’s Theorems on Lengths of Proofs II: Lower Bounds for Recognizing k Symbol Provability Bounded Arithmetic and Propositional Proof Complexity.” In Feasible Mathematics II, edited by P. Clote and J. Remmel 57-90. Basel: Birkhauser. 10.1007/978-1-4612-2566-9_4 Church, Alonso. 1936. “An unsolvable Problem of Elementary Number Theory”. American Journal of Mathematics 58 (2): 345-363. Cook, Stephen. 1971. “The complexity of theorem-proving procedures.” In STOC ’71 Pro- ceedings of the third annual ACM symposium on Theory of computing, 151-158. New York: ACM Association for Computing Machinery. 10.7551/mitpress/12274.003.0036 Davis, Martin and Sigal, Ron and Elaine, Jean. 1994. Computability, complexity and language. Burlington: Morgan Kaufmann. Dawson, John. 1997. Logical Dilemmas. The Life and Work of Kurt Gödel. Wellesley: A K Peters. Dedekind, Richard. 1888. Was sind und was sollen die Zahlen? 1. Auflage. Braunschweig: Vieweg. Du, Dingzhu and Ko, Ker-I. 2014. Theory of Computational Complexity. 2nd Edition. Hoboken: Wiley. Enderton, Herbert B. A mathematical introduction to logic (Second edition). Harcourt/Academic Press: San Diego. 10.1016/C2009-0-22107-6 Feferman, Solomon. 2006. “Are There Absolutely Unsolvable Problems? Gödel’s Dichotomy”. Philosophia Mathematica (III) 14: 134-152. 10.1093/philmat/nkj003 Feferman, Solomon. 2006. “Turing’s Thesis.” Notices of the AMS, Vol. 53 (10): 2-8. 10.2307/j.ctv1vbd2dr.5 Gandy, Robin. 1980. “Church’s Thesis and Principles for Mechanisms.” In The Kleene Symposium, edited by J. Barwise, H. J. Keisler, K. Kunen, K. , 123-148. Amsterdam: North- Holland. 10.1016/S0049-237X(08)71257-6 Gödel, Kurt. 1930. “Die Vollständigkeit der Axiome des logischen Funktionenkalküls”. Translated by Stefan Bauer-Mengelberg. In Gödel’s Collected Works (1986-2005) 102–23 Gödel, Kurt. 1931. “Über Formal Unentscheidbare Sätze der Principia Mathematica und Verwandter Systeme I.” Monatshefte für Mathematik und Physik 38: 173-198 (reprinted in Gödel’s Collected Works (1986-2005), Vol. I: 144-195 10.1007/BF01700692 Gödel, Kurt. 1986-2005. Collected Works I-V, edited by S. Feferman, J. W. Dawson, Stephen C. Kleene, W. Goldfarb, G. Moore, C. Parsons, R. Solovay and Jean Van Heijenoort. Oxford: Oxford University Press. 10.1093/oso/9780195072556.001.0001 Hájek, Peter and Pudlák, Pavel. 1993. Metamathematics of first order arithmetic. Berlin: Springer. 10.1007/978-3-642-78321-9 Hartmanis, Juris and Stearns, Richard E. 1965. “On the computational complexity of algo- rithms.” Transactions of American Mathematical Society 117 (5): 285-306. 10.1090/S0002-9947-1965-0170805-7 Henkin, Leon. (1950). “Completeness in the Theory of Types”. The Journal of Symbolic Logic”, 15 (2): 81-91. 10.2307/2268698 Hilbert, David and Ackermann, Wilhelm. 1928. Grundzüge der theoretischen Logik. Berlin: Springer. Levin, Leonid. 1973. “Universal search problems.” Problems of Information Transmission 9 (3): 115-116. 10.1007/978-0-387-30164-8_603 Lindström, Per. 1969. “On Extensions of Elementary Logic.” Theoria 35: 1-11 10.1111/j.1755-2567.1969.tb00356.x Lucas, John R. 1961. “Minds, machines and Godel”. Philosophy 36 (137): 112-127. 10.1017/s0031819100057983. Kleene, Stephen C. 1967. Mathematical Logic. New York: Wiley Kreisel, Georg. 1971. “Some Reasons for Generalizing Recursion Theory.” In Studies in Logic and the Foundations of Mathematics 61, edited by R.O. Gandy and C.M.E. Yates 139-198. Amsterdam: Elsevier. 10.2307/2271903 Mal’cev, Anatoli Ivanovic. 1971. The Metamathematics of Algebraic Systems. Collected Papers: 1936–1967. Studies in Logic and the Foundations of Mathematics, Volume 66. Amsterdam: Elsevier. McCulloch, Warren S. and Pitts, Walter. 1943. “A Logical Calculus of the Ideas Immanent in Nervous Activity”. Bulletin of Mathematical Biophysics 5: 115-133. 10.2307/2268029 Nelson, Edward. 1986. Predicative Arithmetic. Princeton: Princeton Univ. Press. 10.2307/2274590 Nielsen, Michael A. and Chuang, Isaac L. 2010. Quantum Computation and Quantum Infor- mation: 10th Anniversary Edition. Cambridge: Cambridge University Press. Post, E.L. 1936. “Finite Combinatory Processes - Formulation 1”. The Journal of Symbolic Logic 1: 103-105. 10.2307/2269031 Ryll-Nardzewski, Czesław. 1952. “The role of the axiom of induction in elementary arithmetic”. Fundamenta Mathematicae 39: 239-63. Odifreddi, Piergiorgio. 1989. Classical Recursion Theory I. Amsterdam: North Holland. Sipser, Michael. 2006. Introduction to the Theory of Computation, second edition. Boston: Course Technology. Soare, Robert I. 1996. “Computability and Recursion.” The Bulletin of Symbolic Logic 2 (3) 10.2307/420992 Soare, Robert I. 2009. “Turing oracle machines, online computing, and three displacements in computability theory”. Annals of Pure and Applied Logic 160 (3): 368-399. 10.1016/j.apal.2009.01.008 Soare, Robert I. 2014. “Turing and the discovery of computability”. In Turing’s Legacy: Developments from Turing’s Ideas in Logic. Lecture Notes in Logic, edited by R. Downey 467-492. Cambridge: Cambridge University Press. 10.1017/CBO9781107338579.001 Tait, William. 1981. “Finitism.” Journal of Philosophy 78 (9): 524-546. 10.2307/2026089 Tarski, Alfred and Mostowski, Andrzej and Robinson, Raphael M. 1953. Undecidable Theories. Amsterdam: Elsevier. Turing, Alan M. 1936. “On computable numbers, with application to the Entscheidungsproblem”, in Proceedings of London Math. Soc. 42: 230-265, 544-546. 10.1112/plms/s2-42.1.230 Van Emde Boas, Peter. 1990. “Machine Models and Simulations.” In Handbook of Theoretical Computer Science, Algorithms and Complexity, edited by L. Van Leeuwen, 1-66. Amsterdam: Elsevier. Visser, Albert. 2009. “Why the theory R is special”. Logic Group preprint series, 279. Utrecht Univ. Now in In Friedman, H. and Tennant, N. (eds.) 2014. Foundational Adventures. Essay in honour of Harvey Friedman: 7-23. London: College Publications. 10.1007/s10992-014-9304-0