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

Уважаемые коллеги, приглашаем вас на логический семинар лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ).
Семинар пройдет в среду 4 декабря.
Время проведения семинара 14:30.

МФТИ, радиотехнический корпус, ауд. РТ 113
Институтский пер., 9, стр. 1, Долгопрудный

Ссылка на яндекс-карту с пешим маршрутом от ст. Новодачная:
https://yandex.ru/maps/213/moscow/?ll=37.519439%2C55.929820&mode=routes&rtext=55.924397%2C37.527944~55.929869%2C37.516242&rtt=mt&ruri=ymapsbm1%3A%2F%2Ftransit%2Fstop%3Fid%3Dstation__lh_9601261~ymapsbm1%3A%2F%2Forg%3Foid%3D1109621791&utm_source=share&z=16

В здании пропускной режим, поэтому если у вас нет пропуска в МФТИ, то напишите на почту (kudinov.andrey@gmail.com) заранее.

Заседание пройдет очно без трансляции.

Докладчик: Михаил Рыбаков

Название: Алгоритмическая неразрешимость логики квазиарных предикатов

Аннотация:
Логика квазиарных предикатов предполагает, что язык содержит предикатные буквы, арность которых «варьируется»: в моделях значение предиката определяется на наборе значений сразу всех переменных языка, при этом допускается, что некоторые переменные значений не получили. Такой подход имеет «компьютерную» мотивацию, когда, во-первых, значения у некоторых переменных могу отсутствовать (при выполнении программы), а во-вторых, число элементов, находящихся (или не находящихся) в интересующем нас отношении, может варьироваться (например, когда мы рассматриваем конечный список элементов и требуем его упорядоченность в смысле некоторого предопределённого порядка). Изучением подобных систем занимались М.Никитченко, С.Шкильняк, В.Тимофеев. В частности, было построено погружение многосортной логики квазиарных предикатов в многосортную классическую логику предикатов. В докладе будет показано, как построить погружение классической логики предикатов в логику квазиарных предикатов (уже для односортного случая). При этом для опровержимости перевода исходной формулы будет использоваться модель с тем же носителем, поэтому фактически будет построено и погружение логики конечных моделей в расширение логики квазиарных предикатов, определяемое конечными моделями.

➰ ВК