Семантика игры - Википедия - Game semantics

Семантика игры (Немецкий: диалогическая логика, переводится как диалогическая логика ) - подход к формальная семантика что обосновывает концепции правда или же срок действия на теоретико-игровой концепции, такие как наличие выигрышной стратегии для игрока, несколько напоминающие Сократические диалоги или средневековый теория обязательств.

История

В конце 1950-х гг. Пол Лоренцен был первым, кто ввел игровую семантику для логика, и он был развит Куно Лоренц. Почти одновременно с Лоренценом Яакко Хинтикка разработал теоретико-модельный подход, известный в литературе как GTS (теоретико-игровая семантика). С тех пор в логике изучается ряд различных семантик игр.

Шахид Рахман (Лилль) и соавторы разработали диалогическая логика в общую основу для изучения логических и философских вопросов, связанных с логическим плюрализмом. Начиная с 1994 года это вызвало своего рода возрождение с долгосрочными последствиями. Этот новый философский импульс претерпел параллельное обновление в областях теоретическая информатика, компьютерная лингвистика, искусственный интеллект, а формальная семантика языков программирования, например, работа Йохан ван Бентем и сотрудники в Амстердам который тщательно изучил интерфейс между логикой и играми, и Ханно Никау, который обратился к проблеме полной абстракции в языках программирования с помощью игр. Новые результаты в линейная логика к Жан-Ив Жирар на стыке математической теории игр и логика с одной стороны и теория аргументации а логика, с другой стороны, привела к работе многих других, в том числе С. Абрамский, Я. ван Бентем, А. Бласс, Д. Габбай, М. Хайленд, В. Ходжес, Р. Джагадисан, Г. Джапаридзе, Э. Краббе, Л. Онг, Х. Праккен, Г. Санду, Д. Уолтон и Дж. Вудс, которые поместили семантику игр в центр новой концепции логики, в которой логика понимается как динамический инструмент вывода. .

Классическая логика

Простейшее применение семантики игры - логика высказываний. Каждая формула этого языка интерпретируется как игра между двумя игроками, известная как «Проверяющий» и «Фальсификатор». Проверяющему предоставляется "право собственности" на все дизъюнкции в формуле, и Фальсификатору также дается право собственности на все союзы. Каждый ход игры заключается в том, чтобы позволить владельцу доминирующего соединительного элемента выбрать одну из его ветвей; затем игра будет продолжена по этой подформуле, и любой игрок, контролирующий ее доминирующую связку, сделает следующий ход. Игра заканчивается, когда два игрока сделали такое примитивное предложение; на этом этапе Проверяющий считается победителем, если результирующее предложение верно, а Фальсификатор считается победителем, если оно ложно. Исходная формула будет считаться верной именно тогда, когда Проверяющий получит выигрышная стратегия, в то время как оно будет ложным, если у Фальсификатора есть выигрышная стратегия.

Если формула содержит отрицания или импликации, можно использовать другие, более сложные методы. Например, отрицание должно быть истинным, если отрицаемый объект ложен, поэтому он должен иметь эффект смены ролей двух игроков.

В более общем плане семантика игры может применяться к логика предикатов; новые правила позволяют доминировать квантификатор быть удаленным его "владельцем" (Верификатор для экзистенциальные кванторы и фальсификатор для универсальные кванторы ) и это связанная переменная заменяется во всех случаях объектом по выбору владельца, взятым из области количественной оценки. Обратите внимание, что один контрпример фальсифицирует универсально определенное количественное утверждение, и одного примера достаточно, чтобы проверить экзистенциально количественно определенное. Если предположить аксиома выбора, теоретико-игровая семантика для классических логика первого порядка согласен с обычным модельная (тарская) семантика. Для классической логики первого порядка выигрышная стратегия верификатора состоит в нахождении адекватных Сколемские функции и свидетели. Например, если S обозначает ${ Displaystyle forall х существует у , фи (х, у)}$ затем равноправный заявление для S является ${ Displaystyle существует f forall x , phi (x, f (x))}$. Сколемская функция ж (если он существует) фактически кодифицирует выигрышную стратегию для Проверяющего S возвращая свидетельство экзистенциальной подформулы для каждого выбора Икс фальсификатор может сделать.^[1]

Приведенное выше определение было впервые сформулировано Яакко Хинтиккой как часть его интерпретации GTS. Первоначальная версия игровой семантики для классической (и интуиционистской) логики, разработанная Полом Лоренценом и Куно Лоренцом, была определена не в терминах моделей, а в терминах выигрышных стратегий. формальные диалоги (П. Лоренцен, К. Лоренц 1978, С. Рахман и Л. Кейфф 2005). Шахид Рахман и Теро Туленхеймо разработали алгоритм для преобразования выигрышных GTS стратегий для классической логики в диалогические выигрышные стратегии и наоборот.

Для наиболее распространенных логик, в том числе вышеперечисленных, возникающие из них игры имеют идеальная информация - то есть два игрока всегда знают ценности истины каждого примитива и осведомлены обо всех предыдущих ходах в игре. Однако с появлением семантики игр такие логики, как независимая логика Хинтикка и Санду, с естественной семантикой в ​​терминах игр несовершенной информации.

Интуиционистская логика, денотационная семантика, линейная логика, логический плюрализм

Основная мотивация Лоренцена и Куно Лоренца заключалась в том, чтобы найти теоретико-игровую теорию (их термин был диалогический, на немецком Dialogische Logik [де ]) семантика для интуиционистская логика. Андреас Бласс^[2] первым указал на связь семантики игры и линейная логика. Эта линия была далее развита Самсон Абрамский, Радхакришнан Джагадисан, Паскуале Малякария и независимо Мартин Хайланд и Люк Онг, которые уделяли особое внимание композиционности, то есть индуктивному определению стратегий по синтаксису. Используя семантику игры, упомянутые выше авторы решили давнюю проблему определения полностью абстрактный модель для языка программирования PCF. Следовательно, семантика игр привела к полностью абстрактным семантическим моделям для множества языков программирования и к новым семантически-направленным методам верификации программного обеспечения. проверка модели.

Шахид Рахман [fr ] и Хельге Рюкерт расширили диалогический подход к изучению нескольких неклассических логик, таких как модальная логика, логика релевантности, свободная логика и связная логика. Недавно Рахман и его сотрудники развили диалогический подход в общую структуру, направленную на обсуждение логического плюрализма.

Квантификаторы

Основополагающие соображения семантики игры были более подчеркнуты Яакко Хинтикка и Габриэль Санду, особенно для независимая логика (Логика ЕСЛИ, совсем недавно Информация-дружелюбная логика), логика с кванторы ветвления. Считалось, что принцип композиционности не соответствует этой логике, так что тарскианин определение истины не может обеспечить подходящую семантику. Чтобы обойти эту проблему, кванторам было придано теоретико-игровое значение. В частности, подход такой же, как и в классической логике высказываний, за исключением того, что у игроков не всегда есть идеальная информация о предыдущих ходах другого игрока. Уилфрид Ходжес предложил композиционная семантика и доказал, что это эквивалентно игровой семантике для IF-логик.

В последнее время Шахид Рахман [fr ] и команда диалогической логики в Лилле реализовала зависимости и независимости в рамках диалогических рамок посредством диалогического подхода к интуиционистская теория типов называется имманентное рассуждение.^[3]

Логика вычислимости

Джапаридзе С логика вычислимости представляет собой игровой семантический подход к логике в крайнем смысле, рассматривающий игры как цели, которые должны обслуживаться логикой, а не как технические или фундаментальные средства для изучения или обоснования логики. Его исходный философский пункт состоит в том, что логика предназначена быть универсальным, универсальным интеллектуальным инструментом для `` навигации в реальном мире '' и, как таковая, ее следует истолковывать семантически, а не синтаксически, потому что именно семантика служит мостом между реальный мир и бессмысленные формальные системы (синтаксис). Таким образом, синтаксис вторичен и интересен только в той мере, в какой он обслуживает базовую семантику. С этой точки зрения Джапаридзе неоднократно критиковал часто применяемую практику адаптации семантики к некоторым уже существующим целевым синтаксическим конструкциям с Лоренцен Подход к интуиционистской логике является примером. Затем эта линия мысли утверждает, что семантика, в свою очередь, должна быть семантикой игры, потому что игры «предлагают наиболее полные, последовательные, естественные, адекватные и удобные математические модели для самой сути всех« навигационных »действий агентов. : их взаимодействие с окружающим миром ».^[4] Соответственно, парадигма построения логики, принятая в логике вычислимости, заключается в том, чтобы идентифицировать наиболее естественные и базовые операции в играх, рассматривать эти операторы как логические операции, а затем искать надежные и полные аксиоматизации наборов семантически валидных формул. На этом пути появилось множество знакомых или незнакомых логических операторов открытого языка логики вычислимости с несколькими видами отрицаний, союзов, дизъюнкций, импликаций, квантификаторов и модальностей.

В игры играют между двумя агентами: машиной и ее средой, где от машины требуется следовать только эффективным стратегиям. Таким образом, игры рассматриваются как интерактивные вычислительные задачи, а выигрышные стратегии машины - как решения этих проблем. Было установлено, что логика вычислимости устойчива по отношению к разумным вариациям сложности разрешенных стратегий, которые могут быть уменьшены до логарифмического пространства и полиномиального времени (одно не подразумевает другого в интерактивных вычислениях), не влияя на логику. Все это объясняет название «логика вычислимости» и определяет применимость в различных областях информатики. Классическая логика, независимая логика и некоторые расширения линейный и интуиционистский логики оказываются особыми фрагментами логики вычислимости, полученными просто путем запрета определенных групп операторов или атомов.

Смотрите также

• Логика вычислимости
• Логика зависимости
• Игра Эренфойхта – Фраиссе
• Дружественная к независимости логика
• Интерактивные вычисления
• Интуиционистская логика
• Ludics

Рекомендации

Эта статья включает в себя список общих Рекомендации, но он остается в основном непроверенным, потому что ему не хватает соответствующих встроенные цитаты. Пожалуйста, помогите улучшать эта статья введение более точные цитаты. (Май 2010 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

Библиография

Книги

• Т. Ахо и A-V. Пиетаринен (ред.) Правда и игры. Очерки в честь Габриэля Санду. Societas Philosophica Fennica (2006).ISBN  951-9264-57-4.
• Я. ван Бентем, Г. Хайнцманн, М. Ребуши и Х. Виссер (ред.) Эпоха альтернативной логики. Спрингер (2006).ISBN  978-1-4020-5011-4.
• Р. Инхетвин: Логик. Eine dialog-orientierte Einführung., Лейпциг, 2003 г. ISBN  3-937219-02-1
• Л. Кейфф Le Pluralisme Dialogique. Диссертация Université de Lille 3 (2007).
• К. Лоренц, П. Лоренц: Dialogische Logik, Дармштадт 1978 г.
• П. Лоренцен: Lehrbuch der konstruktiven Wissenschaftstheorie, Штутгарт 2000 ISBN  3-476-01784-2
• О. Майер, А.-В. Пьетаринен и Т. Туленхеймо (редакторы). Игры: объединяющая логику, язык и философию. Спрингер (2009).
• С. Рахман, Über Dialogue protologische Kategorien und andere Seltenheiten. Франкфурт 1993 ISBN  3-631-46583-1
• С. Рахман и Х. Рюкерт (редакторы), Новые перспективы в диалоговой логике. Синтез 127 (2001) ISSN  0039-7857.
• С. Рахман и Н. Клербут: Связывание игр и теории конструктивного типа: диалогические стратегии, CTT-демонстрации и аксиома выбора. Трусы Springer (2015). https://www.springer.com/gp/book/9783319190624.
• С. Рахман, З. МакКонахи, А. Клев, Н. Клербау: Имманентное рассуждение или равенство в действии. Плайдойер для уровня Play. Спрингер (2018). https://www.springer.com/gp/book/9783319911489.
• Дж. Редмонд и М. Фонтейн, Как играть в диалоги. Введение в диалоговую логику. Лондон, College Publications (Col. Dialogues and the Games of Logic. A Philosophical Perspective N ° 1). (ISBN  978-1-84890-046-2)

Статьи

• С. Абрамский и Р. Джагадисан, Игры и полная полнота мультипликативной линейной логики. Журнал символической логики 59 (1994): 543-574.
• А. Бласс, Семантика игры для линейной логики. Анналы чистой и прикладной логики 56 (1992): 151-166.
• D.R. Гика, Приложения семантики игр: от анализа программ до аппаратного синтеза. 2009 24-й ежегодный симпозиум IEEE по логике в компьютерных науках: 17-26. ISBN  978-0-7695-3746-7.
• Г. Джапаридзе, Введение в логику вычислимости. Анналы чистой и прикладной логики 123 (2003): 1-99.
• Г. Джапаридзе, Вначале была семантика игры. Ондрей Майер, Ахти-Вейкко Пиетаринен и Теро Туленхеймо (редакторы), Игры: объединяющая логика, язык и философия. Спрингер (2009).
• Краббе, Э. С. У., 2001. "Основы диалога: восстановление логики диалога [заголовок был напечатан с опечаткой как "... пересмотренный"], " Приложение к Трудам Аристотелевского общества 75: 33-49.
• Х. Никау (1994). «Наследственно последовательные функционалы». В А. Нероде; Ю.В. Матиясевич (ред.). Proc. Symp. Логические основы информатики: логика в Санкт-Петербурге. Конспект лекций по информатике. 813. Springer-Verlag. С. 253–264. Дои:10.1007/3-540-58140-5_25.
• С. Рахман и Л. Кейф, О том, как быть диалогиком. У Даниэля Вандеркена (ред.), Логическая мысль и действие, Springer (2005), 359-408. ISBN  1-4020-2616-1.
• С. Рахман и Т. Туленхеймо, От игр к диалогам и обратно: к общему фрейму действительности. Ондрей Майер, Ахти-Вейкко Пиетаринен и Теро Туленхеймо (редакторы), Игры: объединяющая логика, язык и философия. Спрингер (2009).
• Йохан ван Бентем (2003). «Логика и теория игр: близкие встречи третьего рода». У Г. Э. Минца; Рейнхард Маскенс (ред.). Игры, логика и конструктивные наборы. Публикации CSLI. ISBN  978-1-57586-449-5.

внешняя ссылка

• Домашняя страница Computability Logic
• GALOP: Мастерская по играм для логики и языков программирования
• Семантика игр или линейная логика?
• Томас Пьеха. «Диалогическая логика». Интернет-энциклопедия философии.
• «Логика и игры» запись Уилфрида Ходжеса в Стэнфордская энциклопедия философии
• «Диалогическая логика» запись Лорана Кейффа в Стэнфордская энциклопедия философии