Кафедра математической логики и теории алгоритмов мехмата МГУ

#матлог #спецсеминар #не_мехмат #МФТИ

Уважаемые коллеги, приглашаем вас на логический семинар лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ).
Семинар пройдёт в среду 23 апреля в 14:00.
В рамках этого семинара пройдет предзащита докторской диссертации Рыбакова М.Н.

Место проведения: МФТИ, Административный корпус, ауд. 322,
Первомайская ул. д.7, Долгопрудный.
Чтобы пройти на семинар, если у вас нет пропуска в МФТИ, достаточно сказать, что вы идёте на семинар ВШМ и предъявить паспорт.

К семинару можно подключиться дистанционно, для получения ссылки пишите на почту [email protected].

Докладчик: Михаил Николаевич Рыбаков (ВШМ МФТИ)

Название: Моделирование логических систем средствами их фрагментов (предзащита докторской диссертации)

Аннотация:
Проведённое исследование связано с выразительностью языков, логик и теорий, и прежде всего с алгоритмической выразительностью (в том числе вычислительной сложностью) определённых их фрагментов.

Многие естественные логические системы либо алгоритмически неразрешимы (причём иногда сильно неразрешимы), либо, будучи разрешимыми, имеют высокую сложность проблемы разрешения. Известно, что определённые ограничения, накладываемые на средства языка, аксиоматику или используемую семантику, приводят к изменению алгоритмической сложности тех или иных задач. В то же время иногда это не так: например, в неклассических логиках как неразрешимость, так и высокая сложность проблемы разрешения в случае разрешимости могут получаться при очень сильных ограничениях на средства языка.

Представляется актуальным не только нахождение границ, в рамках которых подобные проблемы оказываются алгоритмически простыми или наоборот остаются алгоритмически сложными, но и разработка общих методов, позволяющих получать оценки алгоритмической сложности фрагментов не только отдельных логических систем, а всех систем тех или иных бесконечных классов. Вместе с методами хотелось бы иметь общие признаки или критерии, позволяющие относительно просто делать вывод об алгоритмической сложности тех или иных фрагментов интересующей нас системы или хотя бы о потенциальной возможности или невозможности применения этих методов.

Основная цель работы состоит в том, чтобы развить общие методы моделирования алгоритмически сложных проблем внутри логик и теорий, используя минимальные средства языка. В частности, в работе предложены методы моделирования полных языков средствами их очень бедных фрагментов. К средствам языка, которые минимизируются, в первую очередь относятся следующие: число пропозициональных переменных в пропозициональных языках, число предметных переменных, а также число и валентность предикатных букв в языках первого порядка. Рассматриваются и некоторые ограничения на использование логических связок и кванторов.

В докладе будет дан обзор результатов, которые были получены автором в этом направлении. Будут коротко описаны методы их получения, а также возможные дальнейшие продвижения.

➰ ВК

VK

Кафедра математической логики МГУ. Пост со стены.

#матлог #спецсеминар #не_мехмат #МФТИ

Уважаемые коллеги, приглашаем вас на логический семинар... Смотрите полностью ВКонтакте.

www.group-telegram.com/sa/msu_mathlog.com/215

620 viewsApr 21 at 16:28

#матлог #спецсеминар #не_мехмат #МФТИ

Уважаемые коллеги, приглашаем вас на логический семинар лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ).
Семинар пройдёт в среду 23 апреля в 14:00.
В рамках этого семинара пройдет предзащита докторской диссертации Рыбакова М.Н.

Место проведения: МФТИ, Административный корпус, ауд. 322,
Первомайская ул. д.7, Долгопрудный.
Чтобы пройти на семинар, если у вас нет пропуска в МФТИ, достаточно сказать, что вы идёте на семинар ВШМ и предъявить паспорт.

К семинару можно подключиться дистанционно, для получения ссылки пишите на почту [email protected].

Докладчик: Михаил Николаевич Рыбаков (ВШМ МФТИ)

Название: Моделирование логических систем средствами их фрагментов (предзащита докторской диссертации)

Аннотация:
Проведённое исследование связано с выразительностью языков, логик и теорий, и прежде всего с алгоритмической выразительностью (в том числе вычислительной сложностью) определённых их фрагментов.

Многие естественные логические системы либо алгоритмически неразрешимы (причём иногда сильно неразрешимы), либо, будучи разрешимыми, имеют высокую сложность проблемы разрешения. Известно, что определённые ограничения, накладываемые на средства языка, аксиоматику или используемую семантику, приводят к изменению алгоритмической сложности тех или иных задач. В то же время иногда это не так: например, в неклассических логиках как неразрешимость, так и высокая сложность проблемы разрешения в случае разрешимости могут получаться при очень сильных ограничениях на средства языка.

Представляется актуальным не только нахождение границ, в рамках которых подобные проблемы оказываются алгоритмически простыми или наоборот остаются алгоритмически сложными, но и разработка общих методов, позволяющих получать оценки алгоритмической сложности фрагментов не только отдельных логических систем, а всех систем тех или иных бесконечных классов. Вместе с методами хотелось бы иметь общие признаки или критерии, позволяющие относительно просто делать вывод об алгоритмической сложности тех или иных фрагментов интересующей нас системы или хотя бы о потенциальной возможности или невозможности применения этих методов.

Основная цель работы состоит в том, чтобы развить общие методы моделирования алгоритмически сложных проблем внутри логик и теорий, используя минимальные средства языка. В частности, в работе предложены методы моделирования полных языков средствами их очень бедных фрагментов. К средствам языка, которые минимизируются, в первую очередь относятся следующие: число пропозициональных переменных в пропозициональных языках, число предметных переменных, а также число и валентность предикатных букв в языках первого порядка. Рассматриваются и некоторые ограничения на использование логических связок и кванторов.

В докладе будет дан обзор результатов, которые были получены автором в этом направлении. Будут коротко описаны методы их получения, а также возможные дальнейшие продвижения.

➰ ВК

BY Кафедра математической логики и теории алгоритмов мехмата МГУ