|
Краткие сообщения
Неразрешимость одноместных PFP-операторов без вложения в теории одного следования
В. С. Секорин Тверской государственный университет, ул. Желябова, д. 33, г. Тверь, 170100, Россия
Аннотация:
В данной работе мы исследуем разрешимость расширений логики первого порядка. Например, в работах А. С. Золотова показано, что логика с унарным оператором транзитивного замыкания для теории следования является разрешимой. Мы показываем, что в аналогичной ситуации логика с унарным оператором частичной неподвижной точки разрешимой не является. Для этого мы сводим проблему остановки счетчиковой машины к проблеме истинности формулы. При этом используется только один оператор частичной неподвижной точки, он является унарным, невложенным и применяется к универсальной или экзистенциальной формуле.
Ключевые слова:
логика первого порядка, частичная фиксированная точка, неразрешимость.
Поступила: 11.01.2024 Исправленный вариант: 11.01.2024 Принята к публикации: 20.03.2024
Образец цитирования:
В. С. Секорин, “Неразрешимость одноместных PFP-операторов без вложения в теории одного следования”, Изв. вузов. Матем., 2024, № 4, 89–93
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/ivm9975 https://www.mathnet.ru/rus/ivm/y2024/i4/p89
|
Статистика просмотров: |
Страница аннотации: | 43 | PDF полного текста: | 1 | Список литературы: | 15 | Первая страница: | 4 |
|