Undecidable Iterative Propositional Calculus


如何引用文章

全文:

开放存取 开放存取
受限制的访问 ##reader.subscriptionAccessGranted##
受限制的访问 订阅存取

详细

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.

作者简介

G. Bokov

Moscow State University, Leninskie Gory

编辑信件的主要联系方式.
Email: bokovgrigoriy@gmail.com
俄罗斯联邦, Moscow, 119992

补充文件

附件文件
动作
1. JATS XML

版权所有 © Springer Science+Business Media New York, 2016