|
This article is cited in 1 scientific paper (total in 1 paper)
Undecidable iterative propositional calculus
G. V. Bokov Faculty of Mechanics and Mathematics, Moscow State University, Leninskie Gory, Moscow, 119992 Russia
Abstract:
We consider iterative propositional calculi that are finite sets of propositional formulas together with modus ponens and an operation of superposition defined by a set of Mal'tsev operations. For such formulas, the question is studied whether the derivability problem for formulas is decidable. In the paper, we construct an undecidable iterative propositional calculus whose axioms depend on three variables. A derivation of formulas in the given calculus models the solution process for Post's correspondence problem. In particular, we prove that the general problem of expressibility for iterative propositional calculi is algorithmically undecidable.
Keywords:
iterative propositional calculus, derivability problem, expressibility problem, Post’s correspondence problem.
Received: 24.09.2015
Citation:
G. V. Bokov, “Undecidable iterative propositional calculus”, Algebra Logika, 55:4 (2016), 419–431; Algebra and Logic, 55:4 (2016), 274–282
Linking options:
https://www.mathnet.ru/eng/al749 https://www.mathnet.ru/eng/al/v55/i4/p419
|
Statistics & downloads: |
Abstract page: | 178 | Full-text PDF : | 44 | References: | 41 | First page: | 12 |
|