Explaining the undecidability of first-order logic
Main Article Content
Abstract
Turing proved the unsolvability of the decision problem for first-order logic (Entscheidungsproblem) in his famous paper On Computable Numbers, with an Application to the Entscheidungsproblem. From this proof it follows that attempts to specify a solution for the Entscheidungsproblem through pattern detection in automated theorem proving (ATP) must fail. Turing’s proof, however, merely predicts the non-existence of such solutions; it does not construct concrete examples that explain why specific attempts to solve the decision problem by pattern detection fail. ATP-search often runs in infinite loops in the case of unprovable, i.e. not refutable, formulas and one can ask why finite patterns of repeated inference steps cannot serve as criteria for unprovability. We answer this question by constructing pairs of formulas (ϕ,ϕ′) such that ϕ is provable (refutable) and ϕ′ is unprovable (satisfiable in an infinite domain) but all but the last proof step of the ATP-search for ϕ is a proper part of the endless ATP-search for ϕ′. We generate such pairs of formulas by mimicking computable sequences for a certain kind of universal Turing machine, namely, splitting Turing machines (STMs), via sequences of inference steps in ATP. In contrast to Turing’s and the textbooks’ method to formalize Turing machines, our method does not rely on further axioms and allows us to transfer the straightforward insight that the halting problem cannot be solved through pattern detection to the case of the Entscheidungsproblem. Our method is a constructive alternative to general undecidability proofs that explains why a scientific problem, namely the Entscheidungsproblem, is unsolvable in a specific way. This explanation provides a better understanding of the failure of pattern detection, which is of interest to: (i) the programmer, who is concerned with prospects and limits of pattern detection, (ii) the logician, who is interested in identifying logical properties by properties of an ideal notation, and (iii) the philosopher, who is interested in proof methods.
Article Details

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
References
Baaz, Matthias, Uwe Egly, and Alexander Leitsch. 2001. Normal Form Transformations. In Handbook of Automated Reasoning Vol. I, edited by John Alan Robinson and Andrei Voronkov, 273–333. Amsterdam et al.: Elsevier / MIT Press. https://doi.org/10.1016/B978-044450813-3/50007-2.
Börger, Egon, Erich Grädel, and Yuri Gurevich. 2001. The Classical Decision Problem. 2. printing of the 1. ed. Universitext. Berlin: Springer.
Dreben, Burton, and Warren D. Goldfarb. 1979. The Decision Problem: Solvable Classes of Quantificational Formulas. Reading, Mass: Addison-Wesley.
Henschen, L., and L. Wos. 1974. Unit Refutations and Horn Sets. J. ACM 21 (4): 590–605. https://doi.org/10.1145/321850.321857.
Lampert, Timm. 2017. A Decision Procedure for Herbrand Formulae without Skolemization. https://doi.org/10.48550/arXiv.1709.00191.
Lampert, Timm. 2018. Iconic Logic and Ideal Diagrams: The Wittgensteinian Approach. In Diagrammatic Represen- tation and Inference, edited by Peter Chapman, Gem Stapleton, Amirouche Moktefi, Sarah Perez-Kriz, and Francesco Bellucci, 624–639. Cham: Springer International Publishing. https://doi.org/10.1007/978-3-319-91376-6_56.
Lampert, Timm. 2020. Decidability and Notation. Logique et Analyse 251:365–386. https://doi.org/10.2143/LEA.251.0.3288645.
Lampert, Timm, and Anderson Nakano. 2020. Deciding Simple Infinity Axiom Sets with One Binary Relation by Means of Superpostulates. In Automated Reasoning, edited by Nicolas Peltier and Viorica Sofronie-Stokkermans, 201–217. Cham: Springer International Publishing. https://doi.org/10.1007/978-3-030-51074-9_12.
Letz, Reinhold, and Gernot Stenz. 2001. Model Elimination and Connection Tableau Procedures. In Handbook of Automated Reasoning, 2015–2114. Elsevier. https://doi.org/10.1016/B978-044450813-3/50030-8.
Neary, T., and D. Woods. 2009. Four Small Universal Turing Machines. Fundamenta Informaticae Vol. 91 (nr 1): 123–144.
Nonnengart, Andreas, and Christoph Weidenbach. 2001. Computing Small Clause Normal Forms. In Handbook of Automated Reasoning, edited by Alan Robinson and Andrei Voronkov, 335–367. Amsterdam: Elsevier. https://doi.org/10.1016/B978-044450813-3/50008-4.
Turing, A. M. 1937. On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society 42 (series 2) (1): 230–265. https://doi.org/10.1112/plms/s2-42.1.230.
Wolfram, Stephen. 2002. A New Kind of Science. Champaign, IL: Wolfram Media. http://www.wolframscience.com/nks/ accessed January 16, 2023.