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

Начинает свою работу логический семинар лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ).
Семинар пройдет в среду 25 сентября. Время проведения семинара 14:00.

Аудитория ГК329 (Главный корпус).
г. Долгопрудный, Институтский пер., 9, стр. 3.

В здании пропускной режим, поэтому если у вас нет пропуска в МФТИ, то напишите на почту kudinov.andrey@gmail.com, вас встретят у центрального входа в главный корпус со стороны Институтского пер. С собой иметь паспорт.

Просьба не опаздывать, т.к. аудитория находится в ректорате и туда так просто не попасть.
Собираемся в 14:00 у дверей в ректорат.

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

Докладчик: М.Н.Рыбаков
Тема: Неразрешимость QLC с двумя переменными

Аннотация:
Логика QLC получается из интуиционистской предикатной логики QInt добавлением аксиомы линейности. Семантически QLC характеризуется классом линейных шкал Крипке. Её модальный напарник — логика QS4.3; она получается из QS4 аналогичным образом. Логика QLC содержит в себе логику QKC (логику слабого закона исключённого третьего), и в этом смысле она очень близка к классической логике предикатов QCl. Известно, что QCl неразрешима в языке с тремя переменными, но разрешима в языке с двумя. При этом и QInt, и QKC, и QS4.3 в языке с двумя переменными неразрешимы (даже при одной-двух унарных предикатных буквах). Техники, используемые в соответствующих доказательствах для фрагментов с двумя переменными, неприменимы к QLC — ни "классическая" с разрешимостью, ни "неклассическая" с неразрешимостью, и вопрос о разрешимости фрагмента QLC с двумя переменными долгое время оставался открытым. Оказалось, имеется довольно несложная конструкция, позволяющая закодировать средствами QLC неразрешимую проблему типа "домино", при это достаточно использовать две переменные и лишь позитивные формулы. В докладе предполагается показать детали этой конструкции и извлечь из неё следствия, касающиеся как QLC, так и некоторого бесконечного класса расширений QLC — во всех случаях будет получена неразрешимость, причём где-то Сигма-0-1-трудность, а где-то дополнительно и Пи-0-1-трудность.

Все необходимые определения будут даны. Тем не менее, для понимания доклада желательно иметь предварительное представление о семантике Крипке для предикатного языка (прежде всего, интуиционистского), а также о неразрешимой (Пи-0-1-полной) проблеме домино, состоящей в выяснении возможности замощения квадратными плитками домино, имеющими типы из данного конечного набора типов плиток, первого квадранта плоскости. В целом, изложение предполагается довольно простым и "в картинках".

➰ ВК