Аннотация:
В данной работе мы исследуем разрешимость расширений логики первого порядка. Например, в работах А. С. Золотова показано, что логика с унарным оператором транзитивного замыкания для теории следования является разрешимой. Мы показываем, что в аналогичной ситуации логика с унарным оператором частичной неподвижной точки разрешимой не является. Для этого мы сводим проблему остановки счетчиковой машины к проблеме истинности формулы. При этом используется только один оператор частичной неподвижной точки, он является унарным, невложенным и применяется к универсальной или экзистенциальной формуле.
Ключевые слова:логика первого порядка, частичная фиксированная точка, неразрешимость.
УДК:
510.624
Поступила: 11.01.2024 Исправленный вариант: 11.01.2024 Принята к публикации: 20.03.2024