• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

Алгоритмическая неразрешимость проблемы первопорядковой определимости формул логики ветвящегося времени

Программные продукты и системы. 2018. Т. 31. № 3. С. 591-597.
Рыбаков М. Н., Чагрова Л. А.

В качестве формального средства, описывающего свойства различных структур (в том числе структур вычислений), обычно используют язык логики предикатов. Этот язык, с одной стороны, понятен и удобен, а с другой, многие вопросы, важные с прикладной точки зрения, для него алгоритмически неразрешимы, то есть не могут быть решены программно. Сейчас существует много альтернативных языков, позволяющих описывать вычисления и их свойства, при этом, в отличие от языка логики предикатов, аналогичные вопросы для них алгоритмически разрешимы. В работе рассматривается один из таких языков – язык логики ветвящегося времени CTL. Он используется для верификации программ, так как содержит средства для описания свойств программных вычислений, в частности, свойств бинарного отношения, возникающего в реляционной семантике Крипке. В работе исследуется возможность алгоритмического нахождения формул языка первого порядка, которые задают те же классы шкал Крипке, что и формулы языка логики CTL. Известно, что для интуицинистских формул проблема их первопорядковой определимости алгоритмически неразрешима. Показано, как, используя перевод Гёделя интуиционистских формул в модальные, а затем перевод получившихся модальных формул в формулы языка логики CTL, свести проблему первопорядковой определимости интуиционистских формул на шкалах Крипке к проблеме первопопорядковой определимости CTL-формул на шкалах Крипке. В качестве следствия такого сведения получена алгоритмическая неразрешимость соответствующей проблемы для CTL. В заключении обсуждаются возможные модификации приведенной конструкции с целью распространения полученного результата на фрагменты языка логики CTL, а также алгоритмическая разрешимость проблемы CTL-определимости формул первого порядка.