Павел Разумный//Об алгоритмической сложности логики QGL, расширенной нефундированными выводами

НИС "Современные проблемы математической логики" в ВШЭ. Дата и время: 31.01.2025 в 16:20 Докладчик: Павел Разумный Название: Об алгоритмической сложности логики QGL, расширенной нефундированными выводами Аннотация: Будет рассматриваться логика QGL_inf - предикатная версия логики Гёделя-Лёба, расширенная нефундированными выводами. Мы докажем, что при достаточно богатой сигнатуре (а именно, содержащей 4 унарных, 3 бинарных и 1 тернарный предикатных символов) к множеству теорем этой логики сводится задача о неостановке машины Тьюринга; из этого факта легко выводится неперечислимость множества теорем QGL_inf. Также будет доказана эквивалентность логики QGL_inf логике QGL c омега-правилом Лёба (обобщение обычного правила Лёба); с помощью данной эквивалентности будет получена верхняя оценка сложности: класс Sigma^1_1 аналитической иерархии.