?
Алгоритмическая неразрешимость проблемы первопорядковой определимости формул логики ветвящегося времени
It is common to use the first-order language as a formal tool for describing properties of various (computational) structures. On the one hand, this language is well understood and easy to use; on the other, many questions that are im-portant from the applications point of view related to this language are algorithmically undecidable, i.e., cannot be answered using a computer program. These days, there exist various alternative languages that can be used for describing computational processes and their properties, for which the corresponding questions are, in contrast to the first-order language, algorithmically decidable. In this paper, we consider one of such languages, – the language of the Computational Tree Logic (CTL). It is commonly used for program verification as it is capable of describing properties of computational processes, – in particular, properties of the binary relation used in the Kripke semantics. The authors investigate the possibility of finding algorithmically first-order formulas defining the same classes of Kripke frames as the formulas of the language of CTL. It is well known the problem of finding first-order correspondents of propositional intuitionistic formulas is algorithmically undecidable. The authors reduce – using the Gödel translation of intuitionistic formulas into modal ones, and subsequently a translation of resultant modal formulas into CTL-formulas – the first-order correspondence problem for propositional intuitionistic formulas to the first-order correspondence problem for CTL-formulas on Kripke frames. As a result of this reduction, they prove that the first-order correspondence problem for CTL-formulas is algorithmically undecidable. In the conclusion, the authors discuss some possible modifications of their construction for fragments of the language of CTL as well as algorithmic decidability of the CTL correspondence problem for first-order formulas.