Игровая семантика логических формул при ограничениях на сложность стратегий. С.Соловьев (25.03.2021)

Игровая семантика логических формул разрабатывалась с целью показать возможность игровой интерпретации (игры между «утвердителем» и «опровергателем», Verifier and Falsifier), которая приводит к стандартной семантике, полученной более традиционным путем. Было показано, что Verifier имеет выигрышную стратегию в игре, построенной по формуле А, в том и только том случае, когда А выводима в соответствующей дедуктивной системе или истинна в модельно-теоретическом смысле.

Хорошо известно, что ограничения на классы стратегий противников могут вести к тому, что этот результат больше не будет иметь места. В связи с этим изучался вопрос о «допустимых» ограничениях: например, возможно ли получить аналогичный результат, рассматривая только вычислимые стратегии. В работе ограничения рассматриваются с другой точки зрения: насколько семантика может быть «искажена» в результате некоторой естественной асимметрии между игроками. С учетом различных типов игр, рассматривавшихся в литературе, в работе рассматриваются, например, игры, в которых один из противников может «брать ход назад». Выясняется, что при наличии ограничений на вычислительную сложность возможны ситуации, когда Verifier имеет выигрышную стратегию для некоторых формул, ложных в обычном смысле. Эти ситуации не выглядят искусственными — например, преимущество Verifier'a может состоять в том, что он способен вычислять универсальную функцию для стратегий Falsifier'a.

Цель работы лежит скорее в практической области, чем в области оснований математики — привлечь внимание к тенденции в современной науке, когда «научным» считается подтверждение, основанное на тестах, а не доказательствах, и «игроки», имеющие доступ к превосходящим вычислительным ресурсам, могут получать неоправданное преимущество.

Докладчик: Соловьев Сергей (Институт информатики Университета Тулузы-3)

Полное название доклада:
Игровая семантика логических формул при наличии ограничений на вычислительную сложность стратегий.
______________________________

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

Веб-страница (слайды, ссылка zoom):