group-telegram.com/msu_mathlog/112
Last Update:
#матлог #учёба #семинар #не_мехмат #ВШЭ
Уважаемые коллеги, приглашаем вас принять участие в заседании научного семинара "Современные проблемы математической логики" в ВШЭ.
Дата и время: 31.01.2025 в 16:20
Семинар пройдет в формате ZOOM, для получения ссылки пишите на почту [email protected].
Видео докладов выкладываются на канале:
https://www.youtube.com/channel/UC_Aq6N03uRgVkEcvS6lJLog
Докладчик: Павел Разумный
Название: Об алгоритмической сложности логики QGL, расширенной нефундированными выводами
Аннотация: Будет рассматриваться логика QGL_inf - предикатная версия логики Гёделя-Лёба, расширенная нефундированными выводами. Мы докажем, что при достаточно богатой сигнатуре (а именно, содержащей 4 унарных, 3 бинарных и 1 тернарный предикатных символов) к множеству теорем этой логики сводится задача о неостановке машины Тьюринга; из этого факта легко выводится неперечислимость множества теорем QGL_inf.
Также будет доказана эквивалентность логики QGL_inf логике QGL c омега-правилом Лёба (обобщение обычного правила Лёба); с помощью данной эквивалентности будет получена верхняя оценка сложности: класс Sigma^1_1 аналитической иерархии.
🔗 Логика в Москве
➰ ВК
BY Кафедра математической логики и теории алгоритмов мехмата МГУ

Share with your friend now:
group-telegram.com/msu_mathlog/112