Содержание к диссертации
Введение
Глава 1. Границы развития интенсиональной доктрины 32
1.1. Проблемы и парадоксы экстенсиональной логики 32
1.1.1. Структур а формализованного языка 33
а) Формальная система 33
б) Семантические правила интерпретации 41
1.1.2. Особенности экстенсионального и интенсионального подходов в логической семантике 46
а) Экстенсиональное направление 47
б) Парадоксы интенсионального контекста 51
в) Революция в интенсиональном направлении 53
1.2. От описания корректности работы программ к описанию работы недетерминированных систем 55
1.2.1. Логика Хоара как альтернатива тестированию 55
1.2.2. Средний терм в динамической логике и логике игр 59
а) Динамическая логика 59
б) От процессов к играм 60
в) Динамическая логика игр 63
1.3. Язык как средний терм при переносе информации 65
1.3.1.Компиляторы и их корректность 65
1.3.2.Проблема передачи знания 68
Глава 2. Подходы к описанию параллельных процессов и игр 77
2.1. Опыт описания параллельных процессов 77
2.1.1. Параллелизм в математике, логике и теоретической информатике 78
а) Алгебра параллельных процессов 78
б) Конкурентная динамическая логика 84
в) Мультипликативная линейная логика 87
г) Сети Петри 94
2.1.2. Параллелизм в теории формальных языков 105
а) Индийская и русская параллельные грамматики 107
б) Системы Линденмайера 109
в) Колонии 111
г) Взаимодействующие распределенные системы грамматик 113
д) Системы эко грамматик 115
е) Параллельные коммуникативные системы грамматик 118
ж) Параллельные коммуникативные системы Линденмайера 124
з) Траектории для операции тасования 126
2.2. Смысл параллелизма для логики 128
2.2.1.Естественнонаучные корни метафоры параллелизма 128
2.2.2.Роль коммуникации для параллельных игр 131
2.3. Альтернирующая динамическая логика игр 134
2.3.1. Уточнение семантики 134
2.3.2. Модель АДЛИ1.1 142
2.3.3. Аксиоматика АДЛИ 1.1 149
Глава 3. Модель ограниченной рациональности для динамической логики игр 151
3.1. Введение в теоретико-игровую семантику 151
3.1.1. Экстенсивная форма. Стратегия и отношение вынуждения 153
3.1.2. Стратегическая форма 159
3.1.3. Учет ресурсов при задании игр , 162
3.2. Ограниченная рациональность 164
3.2.1.Виды дефицита информации 164
3.2.2.Подход к описанию игр с ограниченной рациональностью 167
а) Информированность игроков о состояниях, действиях и стратегиях 167
б) Успешные нити и выигрышные стратегии 170
в) Квазивыигрышная стратегия 172
3.3. Базовые элементы семантики динамической логики игр с ограниченной рациональностью 174
3.3.1.Игра и линейная форма ее представления 174
3.3.2. Отношение вынуждения для игр с ограниченной рациональностью 178
3.3.3. От теоретико-игровых состояний к теоретико-модельным мирам 180
3.3.4. Явные и неявные способы описания миров 181
3.4. Параллельные игры с ограниченной рациональностью 184
3.4.1.Игровая форма и модель игры 184
3.4.2. Синтаксис и семантика 187
Заключение 191
Литература 195
- Особенности экстенсионального и интенсионального подходов в логической семантике
- Взаимодействующие распределенные системы грамматик
- Информированность игроков о состояниях, действиях и стратегиях
- Отношение вынуждения для игр с ограниченной рациональностью
Введение к работе
Логика Хоара была разработана для того, чтобы можно было, избегая тестирования, проверять работоспособность программ и точно описывать выдаваемый результат. Логика Хоара имела ряд недостатков, ограничивающих область ее применения, которые были устранены в динамической логике. В процессе развития вычислительных систем пользователь постепенно стал оказывать все большее и большее влияние на ход выполнения программ. В результате чего потребовался переход к теоретико-игровой семантике. Развитие динамической логики игр, обладающей такой семантикой, может приблизить нас к созданию инструмента для верификации человеко-машинных систем. Подобным многопользовательским системам характерна параллельная обработка информации в условиях ограниченности ресурсов.
Между тем современная логика не имеет достаточных средств, описывающих параллельные системы с ограниченными ресурсами. Большинство логических моделей построено с расчетом на неограниченную рациональность. Эта неограниченность не имеет ничего общего с ответами Оракула, способного, неведомым нам способом, решить любую проблему. Концепция неограниченной рациональности имеет несколько аспектов. Допустим, что человеко-машинная система решает некоторую задачу. Тогда, во-первых, в случае неограниченной рациональности считается, что все участники системы владеют исчерпывающей информацией обо всем, что в ней происходит и находится, или, по крайней мере, существует алгоритм, позволяющий им получить такую информацию. Во-вторых, если эта задача разрешима на машине Тьюринга, то предполагается, что ее решение представлено в описываемой системе, вне зависимости от сложности этой задачи, т.е. затрата материальных и временных ресурсов не учитывается. Саймон (Simon, НА., 1978) в своей Нобелевской лекции подчеркивал эмпирическую ограниченность таких описаний для теории принятия решений. Совершенно очевидна их ограниченность и для прикладных задач информатики. Например, на данный момент не существует «чудо компьютера», способного просчитать все ходы шахмат. Но поскольку шахматы являются конечной игрой с четко определенными ходами, то в случае использования логики, предполагающей неограниченную рациональность, придется считать, что один из игроков имеет выигрышную стратегию. Однако такой подход видится не очень естественным.
За последние сорок лет представлено множество формализации параллельных процессов в теоретической информатике и теории формальных языков. Существует и математическая модель: алгебра параллельных процессов. К сожалению, в логике эта тема почти не отражена. Этот факт показывает не консервативность логики, а технические трудности представления параллелизма логическими средствами, без нарушения существующих концепций. Помимо того, что новые операторы/связки нужно суметь связать со старыми, с помощью новых операторов нужно попытаться выразить нечто новое, не сводимое к уже известным операторам. Иначе особого смысла нововведения иметь не будут.
Параллелизм в логике представлен в теоретико-игровой интерпретации линейной логики, идеи которой были использованы мной при создании первого расширения динамической логики игр на параллельные операторы. Это расширение позволило выявить некоторые свойства и закономерности, присущие параллельным играм. Оказалось, что, в случае этого расширения, параллельные операторы не сводимы к непараллельным, только для игр с несовершенной информацией, или подобным им. Была обнаружена и успешно решена проблема кратных миров. К сожалению, параллельные операторы в этом расширении связаны с копирующей стратегией, позволяющей добиваться победы только в двойственных играх. Сама копирующая стратегия кажется несколько искусственной, а область ее применения довольно узкой. Кроме того, такой подход позволяет задавать новые операторы неограниченно, связывая их с новыми стратегиями розыгрыша параллельных игр. При построении новых стратегии могут быть использованы различные основания: структурные особенности игр, соотношение свойств классов игр, и т.п. Для логических систем такие стратегии было бы естественнее связывать с набором предикатов, а не операторами, потому, что логические операторы не должны решать какие-то локальные задачи. Они должны иметь описание, не зависящее от конкретного типа задач. Не смотря на то, что каждая из этих стратегий позволяет построить решение для целого класса игр, обобщения, обосновывающего введение единого, не зависящего от конкретного типа задач, параллельного оператора (или нескольких операторов), с их помощью получить нельзя. Для нахождения общего основания введения параллельных операторов, полезно будет выяснить: почему одну пару игр мы считаем параллельной, а другую нет.
Еще одной системой, описывающей параллельные процессы, является конкурентная динамическая логика. Однако, во-первых, использование теоретико-игровой семантики для этой логики совсем не очевидно, а, во-вторых, способ определения оператора совмещения мне представляется довольно спорным. Он идет вразрез с теоретико-модельной семантикой Крипке, согласно которой, вычислительный процесс не может оказаться одновременно в нескольких мирах. Я вовсе не считаю, что от семантики Крипке нельзя отклоняться, но, по-моему, это следует делать только в случае крайней необходимости.
Повсеместное распространение сетевых решений, в частности благодаря развитию телефонных коммуникаций и Интернета, поднимают вопрос о гарантиях стабильности работы создаваемых систем. Проверка работоспособности таких систем путем эксплуатации, или тестирования, в течение определенного промежутка времени не способна показать отсутствие ошибок, а лишь позволяет выявлять некоторые из них. Учитывая повсеместное внедрение сетевых решений, следует ожидать, что цена не выявленных ошибок может оказаться огромной.
Исходя из сказанного, анализ аспектов параллелизма, которые могут быть выражены в логике, расширение динамической логики игр на параллельные операторы, и исследование моделей игр с ограниченной рациональностью представляются актуальными.
Степень разработанности темы
В 50е-60е годы XX века появились и теория игр, за вклад в которую Харсани (Harsanyi), Нэш (Nash) и Селтен (Selteri) в 1993 году получили Нобелевскую премию, и, связанные с ней, математические логические игры (Lorenzen, Ehrenfeucht/Fraisse, Hintikka). В те же годы была предложена и теория ограниченной рациональности, за вклад в которую Леонид Витальевич Канторович в 1975 и Саймон в 1978 году получили Нобелевские премии, и сети Петри (Petri), с помощью которых были выделены основные аспекты распределенных параллельных систем, как концептуально, так и математически.
Модели, позволяющие описывать различные аспекты параллельных процессов, представлены в алгебре параллельных процессов, конкурентной динамической логике (Peleg, D., 1987), теоретико-игровой интерпретации мультипликативной линейной логики (Blass, А., 1992), в различных системах грамматик теории формальных языков, включающих системы Линденмайера, эко грамматики, колонии. В теоретической информатике такими моделями являются сети Петри и я - исчисление. К ним же можно отнести методы эволюционного и генетического программирования.
Впервые теоретико-игровая интерпретация операторов динамической логики была предложена Парихом (Parikh, R., 1985). Впоследствии динамическая логика игр, вместе с другими логиками игр и логическими играми, активно исследовалась в Университете Амстердама группой, возглавляемой проф. Ван Бентемом (van Benthem, J., 2002В). Разновидности динамической логики игр и их применение отражены в диссертации Марка Паули (Pauly, М., 2001В). Описание игр с ограниченной рациональностью в логике действий изложено в диссертации Хуанга (Huang, Zh., 1994). Первое расширение динамической логики игр на параллельные операторы представлено в моей магистерской диссертации, выполненной в Университете Амстердама (Netchitailov, Iou.V., 2001 А).
Цель и задачи исследования
Главная цель данного диссертационного исследования состоит, во-первых, в выявлении аспектов параллелизма, которые могут быть выражены в логике, и, в частности, в динамической логике игр. Во-вторых, в создании модели ограниченной рациональности, совместимой с языком динамической логики игр, и, в-третьих, в расширении динамической логики игр на параллельные операторы. Для достижения поставленной цели в диссертации решаются следующие задачи:
раскрываются мотивы использования интенсиональных логик, и исследуются их выразительные возможности обосновываются причины введения параллельных операторов и ограниченной рациональности в динамическую логику игр анализируются некоторые способы представления параллельных процессов в математике, логике, теории формальных языков и теоретической информатике анализируются естественнонаучные корни метафоры параллелизма, и выявляется специфика использования атрибута параллельности в логике анализируются существующие теоретико-игровые формы представления игр рассматриваются варианты представления игр в динамической логике игр анализируются возможные причины дефицита информации и способы их описания в теории игр
Методология исследования
Причины введения параллельных операторов и ограниченной рациональности обосновываются в результате анализа проблем передачи знания. При этом проводится аналогия между гносеологическим подходом к этой проблеме и подходом теоретической информатики. При изучении существующих способов представления параллельных процессов, а так же теоретико-игровых форм используется междисциплинарный сравнительный анализ и метод анализа источников. При создании модели игр с ограниченной рациональностью, на примере шахмат, проводится структурный анализ стратегий, знаний и поведения игроков. При расширении динамической логики игр на параллельные операторы используется принцип «бритвы Оккама».
Научная новизна диссертационного исследования
Научная новизна диссертации может быть кратко сформулирована в следующих положениях:
проанализирована полнота выразительных средств интенсиональных логик, и исследованы их возможности при описании межъязыковых коммуникаций предложена мотивация введения параллельных операторов и ограниченной рациональности в динамическую логику игр проведено междисциплинарное исследование и систематизация опыта описания параллельных процессов построена модель динамической логики игр с параллельными операторами: альтернирующая динамическая логика игр построена модель игр с ограниченной рациональностью выделены возможные причины, по которым игроки могут не достигать целей в играх с ограниченной рациональностью определена линейная форма игры, с помощью которой можно представлять игры с ограниченной рациональностью в динамической логике игр для динамической логики игр предложен способ представления игр с произвольным положительным числом участников построена модель динамической логики игр для параллельных игр с двунаправленной коммуникацией, ограниченной рациональностью и произвольным положительным числом участников
Апробация работы
Некоторые материалы данного исследования изложены в публикации, изданной в научной серии Университета Амстердама, а также были представлены на одном из выступлений в Институте Логики, Языка и Вычислений (Университет Амстердама).
Материалы данного исследования представлялись в виде публикаций тезисов и докладов на следующих конференциях:
«Третьи Смирновские чтения», Сектор логики Института философии РАН, май 2001;
«Седьмая Общероссийская Конференция Современная логика: проблемы теории, истории и применения в науке», СПбГУ, Санкт-Петербург, июнь 2002;
«Международная Научная Конференция: Информация Коммуникация Общество ИКО2002», ЛЭТИ, Санкт-Петербург; ноябрь 2002;
«Четвертые Смирновские чтения», Сектор логики Института философии РАН май 2003;
«Международная Научная Конференция: Информация Коммуникация Общество ИКО2003», ЛЭТИ, Санкт-Петербург; ноябрь 2003;
Отдельные положения диссертации использованы автором при проведении серии семинаров «Логика, Игры, Коммуникация» в Санкт-Петербургском Государственном Университете. Диссертационные исследования поддержаны РГНФ: грант на 2003 год. Некоторые материалы данного исследования опубликованы в сборнике «Логические исследования» за 2003 год. Диссертация обсуждена на заседании кафедры логики философского факультета СПбГУ.
Структура и объем диссертации
Диссертация изложена на 200 страницах. Общая структура диссертационного исследования определяется её основной целью и задачами. Текст диссертации содержит введение, три главы, заключение и список литературы из 75 наименований на русском и английском языках.
ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении обосновывается актуальность темы исследования, показывается степень ее разработанности, определяются цели и задачи исследования, указывается методология и научная новизна диссертации. Кратко излагается структура и основное содержание диссертации.
В первой главе «Границы развития интенсиональной доктрины» раскрываются мотивы использования интенсиональных логик, рассматриваются их выразительные возможности, сравниваемые с возможностями экстенсиональных логик. На основе анализа проблемы средней формулы, проводится исследование полноты выразительных средств интенсиональных логик. Обосновываются причины введения параллельных операторов и ограниченной рациональности в динамическую логику игр, и очерчивается круг-проблем, описываемых с их помощью.
В первом разделе первой главы «Проблемы и парадоксы экстенсиональной логики» раскрывается один из мотивов использования интенсиональных логик. Он связан с парадоксами, возникающими при интерпретации интенсиональных контекстов средствами экстенсиональных логик. Эти парадоксы «естественным образом» устраняются при переходе к интенсиональным логикам. Данный переход стал возможным благодаря семантике Крипке, позволившей совершить революционный шаг в развитии интенсиональных логик. Демонстрация важности интенсиональных логик опирается на тезис о том, что интенсиональные контексты невозможно полностью исключить из научного языка (антитезис экстенсиональности).
Для выполнения данных рассуждений, анализируется различие и особенности экстенсионального и интенсионального подходов в логике. Поскольку экстенсиональные и интенсиональные логики относятся к классу формализованных языков, предварительно описывается структура этого класса. В формализованном языке выделяются формальная и семантическая составляющие. Обсуждаются правила семантической интерпретации. Рассматриваются способы их связи с формальными системами.
В рамках данной диссертационной работы проводится междисциплинарное исследование опыта описания параллельных процессов. Базовые определения формальных систем, в той или иной мере, отличаются в логике, математике, теории формальных языков и теоретической информатике. Между тем, они столь элементарны, что специалист, при переходе из одной области в другую может даже не задуматься о возможном различии, что естественно может привести к неверным интерпретациям. Поэтому, в данном разделе, представляется целесообразным рассмотрение основ теории формальных систем и сравнительный анализ их использования в указанных дисциплинах.
Во втором разделе первой главы «От описания корректности работы программ к описанию работы недетерминированных систем» приводится еще один мотив использования интенсиональных логик: на их основе можно попытаться разработать эффективное средство для верификации программ, избегая метод «слепого» тестирования. Помимо того, что данный пример интересен сам по себе, он может быть полезен в том случае если кому-то вдруг удастся доказать тезис экстенсиональности, или же кто-то просто не согласен с антитезисом экстенсиональности. В таком случае, мотивация, изложенная в предыдущем разделе, может быть «запятнана». В результате, данный пример выступит и в роли «спасательного круга».
Исторически, первым примером логической системы, предназначенной для верификации программ, является логика Хоара. Как известно, слепое тестирование, затрачивая огромные временные ресурсы, не способно доказывать корректность программ. Оно способно лишь «слепо натыкаться» на ошибки, и, таким образом, выявлять некорректность программ.
При декомпозиции, в структуре почти всех сложных программ можно выявить последовательно исполняющиеся блоки. В виде программного кода эти блоки выглядят независимо, оттого и выделяются в качестве блоков, однако в процессе вычисления они связываются между собой передаваемыми основными и промежуточными данными. На входе и выходе сложной программы могут определяться одни данные, тогда как на промежуточных входах и выходах блоков они обычно дополняются данными, являющимися вспомогательными.
Ключевой идеей логики Хоара, позволяющей избежать «слепого» тестирования, является идея использования свойства-инварианта по отношению ко всем блокам рассматриваемой программы, т.е. свойства, которое будучи заданным на входе каждого блока, сохраняется и на выходе. Инвариантные свойства и промежуточные данные в логике Хоара записываются на языке предикатов первого порядка.
В таком случае за один программный цикл можно доказать, вычисляет ли данная программа некоторое свойство. Для этого нужно проверить инвариантность этого свойства по отношению к блокам в процессе выполнения программы. То есть инвариантность этого свойства не должна рассматриваться изолированно для каждого блока. При переходе от блока к блоку не следует терять и промежуточные данные. К сожалению, с прикладной точки зрения, логика Хоара оказалась не эффективной в силу отсутствия алгоритма получения свойства-инварианта для данной программы, или получения программы, сохраняющей данное свойство.
Помимо этого, логика Хоара имеет свойство, делающее ее неполной. Не смотря на то, что промежуточные данные, передаваемые между двумя последовательными блоками программы, должны существовать всегда, они могут оказаться невыразимыми на языке предикатов первого порядка. Подобного рода проблемы можно классифицировать как проблемы невыразимости средней формулы. Периодически возникающие проблемы невыразимости способствовали развитию логических систем.
Возникновение данной проблемы в логике Хоара мне видится результатом того, что или язык, на котором пишутся программы, выходит за пределы первопорядковой логики, или же связь между элементами программы (ветвление, параллелизм) не представимы на языке этой логики.
Пратт решил проблему невыразимости средней формулы, присутствовавшую в логике Хоара, расширением языка логики первого порядка, посредством программной модальности, до языка динамической логики.
В процессе развития вычислительных систем пользователь постепенно стал оказывать все большее и большее влияние на ход выполнения программ. Появился термин: человеко-машинная система. Если пытаться описывать такие системы средствами динамической логики, то снова возникнет проблема невыразимости средней формулы. Для ее устранения нужно перейти к теоретико-игровой семантике. В результате чего понятие процесса будет заменено понятием игры. То, что называется игрой в логике игр и теории игр является абстрактным математическим объектом. Причиной создания таких объектов стала потребность моделирования процессов, ход выполнения которых не однозначен и зависит от внешнего, алгоритмически не заданного вмешательства.
Таким образом, на проблему неустранимости средней формулы можно взглянуть как на одну из причин эволюции интенсиональной логики от логики Хоара к динамической логике игр.
В третьем разделе первой главы «Язык как средний терм при переносе информации» продолжено исследование выразительных возможностей интенсиональных логик и полноты их выразительных средств. Проанализированы их возможности в описании межъязыковых коммуникаций. Предложена мотивация введения параллельных операторов и ограниченной рациональности в динамическую логику игр, и очерчена область проблем, на решение которых подобная логика может быть направлена.
В ходе исследования в данном разделе проводится аналогия между гносеологическим подходом к проблеме передачи знания и подходом теоретической информатики. Выполняется сравнительный анализ этих подходов, позволяющий добиться некоторой ясности в данном вопросе.
Вначале выделяются объектная и операционная семантики. Язык программ высокого уровня обладает объектной семантикой, соответствующей обычной теоретико-модельной семантике формализованных языков. Такие программы апеллируют к абстрактным математическим объектам, возможно функциям. Язык машинных кодов обладает операционной семантикой, являющейся представлением того, что происходит внутри компьютера, когда выполняется откомпилированная программа. Аналогично двумя способами можно рассматривать и естественный язык: с одной стороны, в терминах некоторой теории смысла, и, с другой стороны, связывать язык с поведением.
Операционная семантика не фиксирует объектной семантики. Мы знаем, что делает программа, но мы просто не уверены, как точно интерпретировать ее поведение. В результате мы получим точный компьютерный аналог знаменитого тезиса неопределенности Куайна. Как представлял Куайн, антрополог, высадившийся на далеком острове, будет иметь огромную проблему при составлении разговорника доселе неизвестного языка, на основе наблюдаемых высказываний аборигенов. Проблема "радикального перевода" исключительно посредством наблюдения столкнется с теми же трудностями, что и попытка интерпретации некоторой программы только посредством наблюдения за работой ее откомпилированной версии.
В процессе исследования выделено свойство объектной семантики: неоднозначность объектной семантики останется независимо от того, сколько нам известно об операционной семантике.
Благодаря этому, на примере процесса передачи знания, можно построить модель, которая доказывала бы следующее утверждение: для любой формальной системы существует модель, для которой, несмотря на то, что средняя формула существует, она является невыразимой на языке этой формальной системы. То есть, из-за неустранимости проблемы средней формулы, проблемы естественного языка невозможно «окончательно» сформулировать ни в одной формальной системе.
Характер того, каким образом абориген, будучи ребенком, получил связь своей объектной и операционной семантики (т.е. приобрел языковые навыки), и характер того, каким образом эту связь пытается получить антрополог, по-видимому, существенно отличается. Главное отличие в том, что первый процесс можно считать скорее биолого-лингвистическим, в то время как второй - скорее формально-лингвистическим. Этим можно попытаться объяснить, почему антропологу не удается формально фиксировать объектную семантику с помощью операционной, в то время как абориген никаких трудностей употребления языка не испытывает. То есть здесь дело не в том, что операционная семантика, в принципе, не фиксирует объектной семантики, а в том, что их связь не является формальной.
Более того, объектная и операционная семантики взаимообусловлены, и, в структуре языка, не могут существовать друг без друга. Без операционной семантики не будет инструмента, позволяющего сделать первый шаг для наполнения объектной семантики. Отказ от объектной семантики приведет к тому, что, или нечего будет наполнять, или операционная семантика сама станет объектной. Похоже, что младенцы, вначале усваивают операционную семантику, в процессе контекстуальной ориентации, и лишь, затем, ребенок начинает опираться на приобретенную операционную семантику, как на объект, в результате чего, получает объектную семантику.
В пользу того, что ребенок не приобретает языковые навыки формально-лингвистическими методами можно высказать множество аргументов. Во-первых, младенец изначально не владеет ни объектной, ни операционной семантикой. Во-вторых, формальным методам ребенка, обычно, никто не учит, он просто погружается в языковую среду. В-третьих, эта языковая среда столь нетривиальна, что до сих пор не поддается даже приближенным формальным описаниям. В-четвертых, даже взрослый, четко знающий формальные методы, тратит на изучение языка много лет, и, все равно, не достигает того, чего ребенок способен достичь в первые пять-семь лет своей жизни. И самое главное, ребенок способен получить свои первые языковые навыки лишь до определенного возраста, связанного, скорее всего, с развитием головного мозга, после которого дети не получившие таких навыков утрачивают способность к их приобретению.
Данный вывод согласуется с выводом Серля о том, что человеческие ментальные процессы, в общем, и в языке, в частности, не могут быть сведены лишь к вычислениям и поведению. Поведение, и, в частности, "вычисления" человеческого мозга порождены самой природой мозга. Компьютерные же программы не являются результатом эволюции самих компьютеров, а установлены искусственно и не зависят от того, на чем им предстоит быть реализованными.
При формализации процесса изучения языка и исследовании проблем формально-лингвистической коммуникации, согласившись с неустранимостью проблемы средней формулы, можно обратиться к поиску оптимального соответствия сопоставляемых языков. Для этого полезно использовать динамическую логику игр с параллельными операторами и ограниченной рациональностью, позволяющую, благодаря семантике Крипке, описывать динамику процессов, и статичность фиксированных для описания моментов реальности.
Во второй главе «Подходы к описанию параллельных процессов и игр» проводится междисциплинарное исследование и систематизация опыта описания параллельных процессов, анализируются естественнонаучные корни метафоры параллелизма, и выявляется специфика использования атрибута параллельности в логике. Представляется модель динамической логики игр с параллельными операторами: альтернирующая динамическая логика игр.
В первом разделе второй главы «Опыт описания параллельных процессов» анализируются некоторые способы представления параллельных процессов в математике, логике, теории формальных языков и теоретической информатике
В рассмотренных формальных системах понятие параллелизма, в одних случаях, используется для описания полностью независимых процессов/игр, в других случаях, напротив, для описания взаимозависимых процессов с непосредственной или опосредованной связью. К процессам с непосредственной связью относят процессы, взаимодействующие внутри сети, с целью перестройки своей структуры, а также с целью корректировки, или достраивания путей решения проблем. К процессам с опосредованной связью относят процессы, использующие общую среду обитания, общие ресурсы: решение проблем с помощью распределенных систем, конференции с удаленным доступом, экологические системы.
Благодаря анализу конкурентной динамической логики получено, что описание полностью независимых параллельных игр средствами логики, потребует принципиального изменения семантики Крипке
Во втором разделе второй главы «Смысл параллелизма для логики» анализируются естественнонаучные корни метафоры параллелизма, выявляются аспекты параллелизма, которые могли бы быть описаны с помощью логического аппарата, предъявляются требования к параллельным играм.
Атрибут параллельности, для процессов, обычно употребляется как синоним одновременности. При этом ему противопоставляется последовательность. Заметим, что для четырехмерного многообразия в теории относительности понятие одновременности теряет смысл точно так же как понятие параллельности при его расширении на четырехмерные процессы, а именно, оказывается неопределенным понятием.2
Логика игр благодаря использованию теоретико-игровой семантики имеет свою специфику применения атрибута параллельности. Электрические цепи (релейно-контактные схемы) служат одной из моделей операторов булевой алгебры. В частности конъюнкция и дизъюнкция интерпретируются как последовательное и параллельное соединение соответственно. Однако, не смотря на это, такая логика игр не способна дать средство для описания параллельных процессов. Она позволяет проводить рассуждения об играх безотносительно к порядку их выполнения. Важен лишь факт их выполнения или невыполнения. А значит одновременность выполнения, один из синонимов параллельности, выразить с ее помощью невозможно. Нужно иметь средство для описания порядка выполнения игр.
В динамической логике за порядок выполнения отвечает оператор последовательной композиции. Поэтому кажется вполне естественным, на основе анализа его особенностей попытаться построить оператор «параллельной композиции». Как следствие, для параллельной композиции а 11Р предполагается полная взаимозависимость игр. Для того чтобы удовлетворять данному требованию каждая из игр или должна иметь какой-либо дефицит информации, восполняемый в процессе параллельной игры, или допускать модификацию данных как, например, в немонотонной логике.
Формально это означает, что каждая из игр, связываемых таким оператором параллельной композиции, должна содержать открытый параметр, получающий значение извне. В противном случае, выполнение этих игр будет независимым, и, следовательно, не требующим одновременности. Более того, средств "булевой логики игр" будет вполне достаточно для их описания.
Для передачи значений открытым параметрам, между параллельными играми должен происходить обмен информацией. Игры, между которыми не происходит взаимообмен информацией, не должны называться параллельными. Таким образом, коммуникация между играми является необходимым условием введения параллельных операторов.
В третьем разделе второй главы «Альтернирующая динамическая логика игр» представлена авторская модель расширения динамической логики игр на параллельные операторы. При этом были использованы идеи теоретико-игровой интерпретации мультипликативных связок линейной логики.
Переход к использованию параллельных операторов, сопряжен с трансформацией обычных, одинарных состояний дерева игры, в кратные. Для того чтобы не противоречить семантике Крипке, возможностью расположения сразу в нескольких мирах, с одной стороны, и противоречивостью этих миров, с другой стороны, будем сводить кратные составляющие, получаемые на одном шаге игры, в один мир, но при этом выделять в нем для каждой составляющей отдельные зоны («внутренние миры»).
Формализация альтернирующей динамической логики игр (АДЛИ) была выполнена, на основе слегка модернизированной модели Паули, и с использованием изложенных в работе Бласса принципов игровой семантики для мультипликативных операторов линейной логики. В процессе приведения языка выигрышных стратегий Бласса к языку ф7-стратегий Паули, была обнаружена возможность двух принципиально различных, с семантической точки зрения, вариантов АДЛИ, названных АДЛИ 1 и АДЛИ 2. Возможность подобного разделения дала различная трактовка одного из самых выразительных средств логики игр - оператора дуальности. Разница между этими двумя вариантами коснулась также и того, какие типы игр могут быть использованы для подтверждения основной аксиомы - аксиомы копирующей стратегии: [7i7id] 7t7td)(p.3 Другими словами, для АДЛИ 1 и АДЛИ 2 типы игр, для которых копирующая стратегия становится ф - стратегией различаются. Кроме того, благодаря детальному анализу и строгой формализации первоначального расширения логики игр на параллельные операторы {Netchitailov, lou.V., 2001), была обнаружена его избыточность. Как следствие, были выделены минимальные АДЛИ, которые получили добавочный индекс: «точка два», в то время как «избыточные» варианты стали обозначаться с добавочным индексом: «точка один». Появление минимальной АДЛИ не изменило интерес к предшествующим описаниям, поскольку минимальный вариант применим только для крайне узкого класса игр, в которых копирующая стратегия является ф7- стратегией.
Несмотря на то, что аксиоматика АДЛИ 2.2 не была рассмотрена, можно рассчитывать на подтверждение большинства аксиом АДЛИ 1.1. Однако, при этом, совершенно очевидно, что только для АДЛИ 2 будет верна аксиома t= (сс)ф - (а -іф, в то время, как только для АДЛИ 1 будет верна аксиома t= (сс ф - [ос ]ф. Данные аксиомы, определяют суть различия в аксиоматике между этими двумя вариантами.
В третьей главе «Модель ограниченной рациональности для динамической логики игр» представляется модель игры с ограниченной рациональностью, для чего, вначале анализируются существующие теоретико-игровые формы представления игр. Рассматриваются возможные причины дефицита информации и способы их описания в теории игр. Затем на основе предложенной модели игр с ограниченной рациональностью, представляется модель динамической логики игр для параллельных игр с двунаправленной коммуникацией, ограниченной рациональностью и произвольным положительным числом участников.
В первом разделе третьей главы «Введение в теоретико-игровую семантику» анализируются экстенсивная и стратегическая (нормальная) формы игры. Поднимается вопрос об учете ресурсов при задании игр.
Получено, что если для отношения вынуждения условие монотонности выполняется всегда, то для стратегии в случае игр ограниченной рациональностью условие монотонности не выполняется. Подобное расхождение свойств отношения вынуждения и стратегии не существенно для детерминированных конечных игр. Для таких игр предполагается, что игрок знает все стратегии априори. Значит, он сможет идентифицировать нити, дающие финальные состояния отношению вынуждения, но не входящие в стратегию рассматриваемого игрока. В результате, отказавшись от выбора данных нитей в процессе игры, он сможет гарантировать окончание игры в пределах исходной стратегии, т.е. исходного подмножества отношения вынуждения. Однако после введения ограничения на рациональность игроков, а именно, на их знание о стратегиях, отмеченное здесь различие нужно будет учитывать. Для этого будет переопределено отношение вынуждения.
Стратегии для нормальной формы игры не могут быть монотонно расширены. Но если в случае стратегий для игр, записанных в экстенсивной форме, монотонное расширение невозможно только для некоторых игр, например, с ограниченной рациональностью, то для стратегий, записанных в нормальной форме, оно невозможно никогда. По отношению к свойству монотонности стратегия нормальной формы и отношение вынуждения ведут себя по-разному. Помимо этого не понятно как можно задать ограничение рациональности, основываясь на представлении игры в виде нормальной формы. Поэтому за основу, при построении формы игры для случая ограниченной рациональности, следует взять экстенсивную форму.
Во втором разделе третьей главы «Ограниченная рациональность» анализируются возможные причины дефицита информации и способы их описания в теории игр. При создании модели игр с ограниченной рациональностью, на примере шахмат, проводится структурный анализ стратегий, знаний и поведения игроков, выделяются возможные причины, по которым игроки могут не достигать целей в играх с ограниченной рациональностью. С помощью понятия квазивыигрышной стратегии, очерчивает класс игр с ограниченной рациональностью.
Получено, что относительно друг друга игры с неполной и несовершенной информацией имеют свои плюсы и минусы. К плюсам игр с несовершенной информацией, можно отнести, например, то, что они имеют строгую теоретико-игровую форму. В то же время игры с неполной информацией с теоретико-игровой точки зрения имеют недостаточное описание даже для того, чтобы называться игрой.4 Значит вне параллельной композиции, которая превращала бы их в полноценную игру, они не могли бы применяться. Зато, с другой стороны, игры с неполной информацией не требуют всеобъемлющего знания об отсутствующей информации. В то же время информационные множества игр с несовершенной информацией требуют исчерпывающего описания. В результате класс описываемых игр сужается до тех, для которых мы можем описать все, что нам не известно. Другими словами, в играх с несовершенной информацией нужно уметь полностью формализовать незнание, что в большинстве случаев недостижимо.
Такой элемент игры как стратегия, не обязан быть окончательно определенным до начала игры, а иногда даже и в процессе. Процесс уточнения стратегии, или того, какой стратегией воспользоваться, может продолжаться вплоть до окончания игры. Данный факт играет важную роль при определении свойств операторов логики игр. В самом деле, для логики действий в роли операторов выступают действия, которые должны быть заданы явно, непосредственно до игры, чтобы игра имела теоретико-игровую форму. В логике игр, в отличие от логики действий в роли операторов выступают игры, а наличие или отсутствие у игрока стратегии сопоставляется с модальностями. Поскольку стратегии не обязаны быть окончательно определенными до игры, то и операторы логики игр тоже.
При этом такие игры уже и без использования дополнительных описательных возможностей параллельных операторов являются играми в строгом смысле. Достаточно упомянуть общепринятое представление игр в виде нормальных форм, с характерными для них таблицами результатов для различных последовательностей действий. Для игр, представленных в нормальной форме, игроки могут определить какой из стратегий воспользоваться только для случаев, когда выполняется равновесие Нэша.
Для определяемой модели предположим следующее ограничение рациональности: для конечного числа финальных состояний и нитей игры, вхождение нитей в стратегии не проверяемо. Подобное возможно, например, вследствие незнания игроком алгоритма Цермело, или ограниченности вычислительных ресурсов.
Предполагается, что в условиях ограниченной рациональности, игроки могут воспользоваться квазивыигрышной стратегией, для того, чтобы попытаться форсировать приемлемый для себя результат. Данная стратегия состоит, во-первых, в разбиении сложной задачи, на несколько составляющих, и, во-вторых, с приписыванием каждой задачи промежуточных целей, которые могли бы считаться благоприятными, для успешного решения последующих задач. Подобную тактику используют и шахматисты. В первом приближении, они разбивают одну большую задачу на три последовательных этапа: дебют, миттельшпиль и эндшпиль. На каждом из этапов, в зависимости от локальных целей, они решают отдельную задачу. Совместное решение этих задач, в большинстве случаев, приводит к общему успеху. Так в дебюте целью (задачей) является благоприятное расположение фигур. В миттельшпиле задачей становится достижение материального перевеса, используя благоприятное расположение фигур. Эндшпиль же предполагается завершать постановкой мата, благодаря созданному материальному перевесу.
Для игр с ограниченной рациональностью выделены две причины, по которым игроки в предложенной модели могут не достигнуть целей: одна из них связана с тем, что успешные цели могут не совпадать с финальными состояниями стратегий игрока, а другая связана с несогласованностью промежуточных целей при последовательном разбиении задачи. Данные результаты использованы при построении игровой формы для последующего введения параллельных операторов в логику игр. Первый позволил определить игры с ограниченной рациональностью. Благодаря второму результату был специальным образом переопределен оператор последовательной композиции, в результате чего удалось отделить неявное описание целей от явного. Это важно в свете ограниченности вычислительных ресурсов, поскольку неявное описание требует дополнительных затрат ресурсов в ходе решения поставленной проблемы
В третьем разделе третьей главы «Базовые элементы семантики динамической логики игр с ограниченной рациональностью» определяется линейная форма игры соответствующая предложенному классу игр с ограниченной рациональностью. Задается отношение вынуждения для игр с ограниченной рациональностью, которое уже не удовлетворяет условию монотонности. Определяется переход от теоретико-игровой к теоретико-модельной семантике, выделяются явные и неявные способы задания миров. Вводится понятие характеристических формул, достижение которых способны гарантировать игроки в условиях ограниченной рациональности.
Получено, что при добавлении в язык динамической логики игр параллельных операторов мы вынуждены апеллировать к более тонкой, чем стратегия структуре. При этом в процессе переопределения семантики все же удается удержаться от перехода к использованию действий. В данной работе показано, что достаточно добавить в описание только нити игры. Полученную в результате этого форму назвали линейной формой игры.
Линейная форма игры может служить адекватным средством представления игр, в которых игрок произвольным образом использует цепочки ходов с успешными финальными состояниями, не зная того, принадлежат ли эти цепочки успешным стратегиям.
Линейная форма игры G это кортеж (N, А, Н, D, S), в котором N= {1,2... к] непустое конечное множество игроков А - {а і, «2 dm) непустое конечное множество действий Н = {hi, ІІ2 ...} МНОЖеСТВО НИТеЙ ИГрЫ, ГДЄ hi = (flu, йі2 ... ui„), для / є {1, 2...}, упорядоченные конечные последовательности действий D={Pi, Pi ...} множество диспетчера действий, в котором каждый Рі = (Ріі, Ра ... Pin), где pize{l, 2... к} номер игрока (гє{/, 2... п}), ставится в соответствие с /г,- для одного и того же / є {/, 2...}
S = [so, si, S2...} непустое множество, содержащее начальное состояние игры so и финальные состояния, в котором каждый 5,- ставится в соответствие с hi для одного и того же / є {1, 2...}
Непустой набор нитей игры а, очерчивающий поддерево этой игры, называется стратегией игрока в игре а тогда и только тогда, когда состояния этого поддерева, в которых оппоненты принимают решения, содержат точно такие же, как и в дереве игры а, наборы выходящих непосредственно из них действий.
В четвертом разделе третьей главы «Параллельные игры с ограниченной рациональностью» построена модель динамической логики игр для параллельных игр с двунаправленной коммуникацией, ограниченной рациональностью и произвольным положительным числом участников.
Обозначим выделенного игрока Р (Proponent), а других игроков О (Opponents). В рамках нашей модели мы будем сокращенно обозначать греческой буквой а кортеж {N, А, Н, D, S) линейной формы игры. При этом, игру а в которой выделенный игрок играет на позиции leN, будем обозначать а1, игру в которой он играет на позиции 2eN, будем обозначать а2, и т.д. В таком случае, легко заметить, что тождество (a )d = ос2 означает, что а это игра для двух участников. Кроме того, тождества а1 = а2 = ... = ссп означают, что игроки на всех позициях в игре а обладают равными возможностями.
Задается ограниченное отношение вынуждения для произвольного количества игроков. Ограниченное отношение вынуждения pP(cc)(w, F) выражает то, что игрок на позиции Р в игре а, начавшейся в мире w, имеет стратегию, нити которой заканчиваются финальными мирами, формирующими множество F. Обозначение (w, F) є рр (а) используется как равносильное.
Определены следующие свойства ограниченного отношения вынуждения:
1. немонотонность: из (w, X) є pp(a) иХсУне следует что (w, Y) є p?(a);
2. непротиворечивость: Если (щ Y) є ро(ос) и (w, Z)e pp(a), то YnZ 0 это возможно, когда в каждом состоянии только один игрок обладает правом выбора следующего действия, либо выбор совершается случайным образом;
3. неуправляемость: Пусть рр(сс) = {(ш, Х{), (щХ2),..., (щ Xk)},тогда V[Z= [J (v\(w,Xd є pP(a) & ц є X,)] 3[(м, Y) є Po(a)] (YczZ)
To есть, если взять по одному произвольному миру из каждого множества отношения вынуждения Р, то подмножеству этого множества будет соответствовать одно из отношений вынуждения О. А значит, О сможет форсировать и Y и Z! Данное свойство отражает тот факт, что хотя игрок и может гарантировать достижение одного из миров, принадлежащих одному из множеств его отношения вынуждения, он не в состоянии управлять тем, какой из миров выбранного множества будет достигнут. Более того, этим процессом может управлять соперник.
Параллельные игры а@Р определены следующим образом. Для непустого множества возможных миров X, (w, Х)єрР(а(3) тогда и только тогда, когда 3r,ZcX(Vw er(w,Z)epP(a)«VT(/ GZ(w", Г)єрр(Р)).
Получено, что сохраняется классическое отношение между модальностями [ос](р = -і(сс -іф. Однако данная модель динамической логики игр с ограниченной рациональностью исключает возможность использования редукции (сс;Р)ф = (сс)(Р)ф в обе стороны. С точки зрения семантики последнее означает, что мы не можем определить цели игры (а) через неявную формулу (Р)ф, соответствующую несыгранной игре. Это важно, так как, к примеру, в шахматной партии совершенно бесполезно описывать целевые формулы промежуточного этапа а (например, дебюта) через целевые формулы последующего этапа Р (например, миттельшпиля).
Для операторов динамической логики игр можно провести следующие теоретико-игровые аналогии. С помощью операции теста «ф?» игрок Р проверяет, является ли формула ф выполнимой и явной. С помощью операции объединения «оси3» он выбирает одну из двух игр. Операция пересечения «сспр» соответствует тому, что другие игроки О выполняют выбор между играми а и р. Оператор параллельной композиции аР позволяет форсировать некоторые формулы ф, даже если они не являются характеристическими.
Перейти к определенным ранее играм с двумя участниками можно, задав следующее свойство с помощью оператора двойственности: (w, Х)єрр((а!) ) ttt(w, Х)ерР(а2).
В заключении диссертационной работы подводятся общие итоги исследования, формулируются основные выводы, приведенные в положениях, выносимых на защиту, определяется теоретическое и практическое значение работы, исходя из чего, намечаются перспективы дальнейших исследований. Указывается как, когда, и где диссертация прошла апробацию
Особенности экстенсионального и интенсионального подходов в логической семантике
Начиная с Рудольфа Карнапа, в семантике было принято выделять чистую и дескриптивную часть. На долю чистой семантики, как ветви математики, отводилось определение абстрактных семантических систем, и исследование их свойств. На долю дескриптивной семантики отводилось описание структуры и осмысление конкретных, исторически данных языков. С подобным делением, вплоть до работ Ричарда Монтегю (см. Montague, R., 1974), по разным причинам соглашались и логики и лингвисты. Считалось, что аппарат, разработанный для синтаксиса и семантики формализованных языков, не применим к естественным языкам. Логикам естественные языки казались слишком несистематичными, полными неясностей, многозначными, противоречивыми, в общем, совершенно не подходящими для формализации.
Однако Хомский (Chomsky, N., 1957) и Дэвидсон (Davidson, D., 1967), указывая на приобретение детьми языковых навыков, подчеркивали, что естественные языки, являясь потенциально бесконечными, все же изучаемы. Поэтому они должны быть финитно характеризуемы. Хотя вопрос о том, в каком виде можно построить подобную формализацию (грамматическое описание, аксиоматическое описание, описание с помощью какого-либо автомата, или что-либо еще), до сих пор остается открытым.
Тому, что формализованные языки, используемые в логике, до недавних пор рассматривались отдельно от естественных языков, способствовали, в частности, и трудности, возникавшие при использовании интенсиональных контекстов. Обойтись же одними экстенсиональными, при моделировании естественного языка, похоже, невозможно. Однако после появления в интенсиональной семантике новой, динамичной модели возможных миров ситуация изменилась.
Для краткого пояснения различия между экстенсиональным и интенсиональным контекстами вновь обратимся к силлогистике. Термы суждений могут быть единичными (напр., Дева Мария), или общими (напр., девушка). Использование общих термов значительно отличается в зависимости от того, в каком контексте экстенсиональном или интенсиональном проводится рассуждение. В случае экстенсионального контекста, называемого также денотационным или объектным, каждому общему терму сопоставляется фиксированное множество объектов. В случае же интенсионального контекста, называемого также коннотационным или смысловым, каждому общему терму сопоставляется фиксированное множество признаков или свойств.
В середине XX столетия, шел процесс интенсивного развития модальных логик. При этом было создано множество новых классов модальных логик. Каждая из таких логик была построена на базе экстенсиональной семантики и имела характерную только ей систему аксиом. К сожалению, все эти логические построения тяжело было связать каким-то единым смыслом, который позволил бы использовать их за пределами логики. Обнаружение единой идеи позволило бы перевести эти логические системы из состояния конкуренции в состояние кооперации. Другим минусом было то, что экстенсиональная семантика не позволяла естественным образом интерпретировать многоуровневую вложенность модальных кванторов. Так, интерпретация формул вида: "Возможно, что необходимо, что необходимо, что возможно..." многих приводило в замешательство. А ведь следуя правилам определения формальных систем, довольно трудно придумать способ построения ППФ, в которых разрешен второй уровень вложения модальных кванторов, и при этом не разрешены все последующие. Такое многоголосие и трудность восприятия, посредством экстенсиональной семантики, привели некоторых философов, в частности Куайна, к решению отказаться от модальных и интенсиональных понятий как от безнадежно туманных и размытых. Отказавшись от попыток описания модальных и интенсиональных понятий средствами экстенсиональной семантики, они решили показать, что экстенсиональных понятий вполне достаточно для языка науки.
В экстенсиональной семантике основными синтаксическими категориями являются константы, переменные, условия или открытые термы (выражения со свободными вхождениями переменных) , и утверждения или замкнутые термы (выражения без свободных вхождений переменных). Вслед за Фреге, принято различать смысл и значение, а утверждения считать именами значений истинности. Этим достигается связь языка с тем, что с помощью этого языка выражается. Кроме того, это позволяет выделять формальную систему, модель и реальность. Понятие смысла связывает формальную систему и модель, понятие значения связывает формальную систему и реальность, а присваивание утверждениям значений истинности связывает реальность с моделью.
Проанализировав работы Тарского, Карнапа, Рассела, Фреге, Куайна и других авторов, Черч сформулировал шестнадцать семантических принципов. Вот некоторые из них: (і) каждое понятие является определением только одной сущности, (іі) Смысл константы однозначно определяется понятием. (Ш) Смысловым диапазоном переменной является непустой класс понятий, (iv) Значением константы является сущность, описываемая понятием, определяющим смысл этой константы, (v) Диапазоном переменной является класс сущностей, описываемых понятиями, определяющими ее смысловой диапазон. Две формулы называются равнозначными, если при подстановке произвольной выборки значений вместо свободных переменных они принимают одно и то же значение. Формулы называются тождественными по смыслу, если при подстановке произвольной выборки смыслов вместо свободных переменных они принимают один и тот же смысл.
В пределах экстенсионального направления можно выделить несколько подходов к формированию логической семантики. Один из них это теоретико-множественный подход, предложенный Кантором, который лежит в основе классической логики. Другим является конструктивный подход. Он лежит в основе интуиционистской логики, предложенной Брауэром.
Для определения модели в экстенсиональных логиках, нужно отделить синтаксическую часть языка от семантической. Для этого, с одной стороны, выделяют предикатные символы и предметные константы, которые относят к синтаксису. Они понимаются как различаемые имена, не несущие в пределах синтаксиса какого-либо значения. С другой стороны, к семантике относят некоторые элементы (понятия, сущности) и предикаты, принимающие значение истина или ложь в зависимости от суперпозиции, входящих в них параметров. Параметрами могут быть эти элементы, или другие предикаты.
Взаимодействующие распределенные системы грамматик
Таким образом, параллелизм для сетей Петри предполагает полную независимость процессов. Сети Петри имеют более сложную структуру, чем структура, образуемая отношением достижимости и возможными мирами в семантике Крипке. Было бы интересно попробовать адаптировать какую-нибудь логическую систему для описания семантики сетей Петри, или же, если это не возможно, то попробовать создать новую.
В теории формальных языков, наряду с грамматиками, для которых правила переписывания применяются последовательно, существуют грамматики, для которых правила вывода применяются параллельно. Простейшими примерами являются индийская параллельная грамматика и русская параллельная грамматика (Indian, Russian parallel grammar). В качестве гораздо более сложного и менее изученного примера можно привести системы Линденмайера (Lindenmayer systems).
Кроме того, в последнее десятилетие в теории формальных языков были разработаны параллельные системы, использующие теоретико-игровые понятия агента (agent) и среды (environment). Агентом называют грамматики в самом общем смысле. В качестве деятельности грамматик естественно рассматривать генерирование формальных языков. Средой называют строку символов, доступную для изменения каждому из агентов. Множество агентов взаимодействуют друг с другом или разделяемой ими средой. Попытки применения систем грамматик были направлены на создание аппарата для решения задач распределенных систем (напр., телеконференций), на построение общественных моделей (напр., описание жизни в поликультурной среде), на построение биологических моделей (напр., описание экосистем), и т.п.
В зависимости от свойств агента и среды определяют различные варианты параллельных грамматик, рассматриваемых в этом разделе. Если взять простых агентов, и простую среду, то получим структуру, называемую колонией (colony). В случае если мы вместо простых агентов возьмем сложных, то получим взаимодействующие распределенные системы грамматик (cooperating distributed grammar systems). Структуры со сложной средой называются системами эко грамматик (eco-grammar systems). Кроме того, можно взять простую распределенную среду и сложных агентов. Тогда получим параллельные коммуникативные системы грамматик (parallel communicating grammar systems). Если же в них заменить среду на сложную распределенную, то получим параллельные коммуникативные системы Линденмайера (parallel communicating Lindenmayer systems). Создание систем грамматик позволило увеличить порождающую мощь входящих в них грамматик, и уменьшить описательную сложность способов генерации формальных языков.
И, наконец, самым свежим примером описания параллелизма средствами теории формальных языков являются П-системы (Р systems), изначально появившиеся в виде мембранных вычислений (membrane computing) . Интересные аналогии между теорией формальных языков и алгеброй параллельных процессов позволяет провести определение траектории для операции тасования (shuffle). Грамматики относятся к инструментам, позволяющим генерировать формальные языки.22 Впервые в теории формальных языков к идее параллелизма обратились при создании индийской и русской параллельных грамматик. Эти грамматики имеют структуру обычных формальных грамматик, и отличаются от них только тем как понимается непосредственный шаг вывода.
Формальной грамматикой G называется кортеж (N, T,S,P) с алфавитом нетерминальных символов N, алфавитом терминальных символов Т (N пТ= 0), начальным символом или аксиомой S є JV, и правилами переписывания (продукциями) Р: представляющими собой конечное множество таких пар (х, у), что . у є (NvT) , и и содержит по крайней мере один символ из N. Пару (х у) обычно записывают в виде Xj у.
Во всех вариантах грамматик и систем грамматик теории формальных языков, нетерминальные символы не могут входить в язык, определяемый грамматикой или системой. Нетерминальные символы устраняются в процессе применения правил переписывания. Всевозможные порождаемые грамматикой терминальные строки и образуют генерируемый грамматикой язык.
Для индийской параллельной грамматики = (N, Г, S, Р), шаг вывода и = jr v является непосредственным тогда и только тогда, когда и є (N u Т)+, ve (NuT) и существует такое правило что, во-первых, и = И/Л«2-...Ан :, где и,е ((NU 7)- {Л}) , 1 / , и, во-вторых, v=VizV2...zVk. То есть, в индийской параллельной грамматике все копии одного и того же нетерминального символа переписываются, в соответствии с выбранным правилом вывода, одновременно за один шаг.
Как видно из примера, индийская параллельная грамматика позволяет чрезвычайно просто генерировать язык. В случае последовательных грамматик, для генерации данного языка приходится использовать значительно более сложные, и не столь прозрачные, правила. В русской параллельной грамматике 01 = (N, Т, S, Р), выделяют две группы правил Р = Р] u Р2, Pi пР2 = 0. Они имеют идентичные характеристики правых и левых частей, такие же как и в случае индийской грамматики, т.е. контекстно-свободные: если (А — z) є Pj или Рг» то А є N, ZG (NuT) . Правила одной из групп Р/ применяются последовательно, в то время как правила другой Р2 - параллельно. Как следствие, если Р/ = 0, то из русской параллельной грамматики получаем индийскую, а если же Рг = 0, то получаем контекстно-свободную грамматику, в которой правила применяются исключительно последовательно.
Информированность игроков о состояниях, действиях и стратегиях
В первой работе, описывающей расширение динамической логики игр на параллельные операторы {Netchitailov, 2001А), был исследован лишь один из способов их возможного определения. В той работе параллельные операторы были заданы по аналогии с теоретико-игровой интерпретацией связок, предложенной для линейной логики (Blass, 1992). Копирующая стратегия, на которой было основано определение данных операторов, кажется несколько искусственной, а область ее применения довольно узкой. И все же, не смотря на это, выполненная работа позволила выявить некоторые свойства и закономерности, присущие параллельным играм. Так, при введении параллельных операторов, был использован принцип бритвы Оккама. Другими словами, эти операторы не должны были быть полностью сводимы к операторам, известным ранее. Такой результат оказался достижим для игр с несовершенной информацией. Было выявлено, что если предложенную семантику применить для игр с совершенной информацией, то в аксиоматике параллельные операторы окажутся сводимыми к непараллельным. Кроме того, в процессе проведенного исследования обозначились вопросы, не встречавшиеся до этого в логике игр. Например, проблема задания и использования кратных миров.
В последующем были рассмотрены и другие случаи применения параллельных операторов {Netchitailov, 2001В, Нечитайлов, 2002А). Благодаря этому стало ясно, что если продолжать следовать приемам определения параллельных операторов использованным в данных работах, количество новых операторов будет пусть и не быстро, но неограниченно расти. Дело в том, что в этих работах каждый новый оператор связывался с новой стратегией розыгрыша параллельных игр. Новые стратегии, в свою очередь, могут использовать различные основания для построения: структурные особенности игр, соотношение свойств классов игр, и т.п. Поэтому, не смотря на то, что каждая из этих стратегий позволяет построить решение для целого класса игр, обобщения, обосновывающего введение единого параллельного оператора (или группы операторов), с их помощью получить нельзя. Для нахождения общего основания введения параллельных операторов, полезно будет выяснить: почему одну пару игр мы считаем параллельной, а другую нет. Для этого вначале обратимся к геометрии как наиболее строгому случаю употребления понятия параллельности. Если переносить это понятие на новую предметную область, его смысл будет изменяться. В результате, до логики игр дойдет лишь метафора параллелизма.
Атрибут параллельности изначально применялся только к геометрическим фигурам в пространстве. Именно в геометрии его применение получило строгое определение. Теория относительности связала воедино пространство и время. Поскольку она признана консервативным расширением классической физики, она является и расширением классического представления о пространстве. В рамках этого представления атрибут параллельности также должен иметь возможность расширения. Причем в данном случае он уже будет применяться не к пространственным фигурам, а к пространственно-временным процессам. Так мы получим определение параллельных процессов. Однако для современных прикладных целей такое определение будет бесполезным. Действительно, мы рассматриваем процессы в нашем 3+1 мерном пространстве. А значит, параллельное пространство-время, а вместе с ним и параллельный процесс, должен находиться в параллельной вселенной. Причем процессы в параллельной вселенной вместе с процессами в нашей Вселенной будут образовывать уже пятимерную конфигурацию. В четырехмерной конфигурации они не представимы, т.е. не имеют смысла. Впрочем, даже если параллельные вселенные существуют, на данный момент это не известно и не может быть никак использовано.
Однако, не смотря на это, мы с легкостью употребляем атрибут параллельности для процессов, протекающих в пределах одной, нашей, Вселенной. При этом он обычно понимается как синоним одновременности. С другой стороны, ему противопоставляется последовательность. Для иллюстрации того, что подобное противопоставление имеет место, можно упомянуть деление схем электрических цепей на параллельные и последовательные соединения. Заметим, что для четырехмерного многообразия в теории относительности понятие одновременности теряет смысл точно так же как понятие параллельности при его расширении на четырехмерные процессы, а именно, оказывается неопределенным понятием (см., например, Рассел, 1997, с.307).
Логика игр благодаря использованию теоретико-игровой семантики имеет свою специфику применения атрибута параллельности. Рассмотрим для начала логику игр, заданную на основе булевой алгебры. Электрические цепи (релейно-контактные схемы) служат одной из моделей операторов булевой алгебры. В частности конъюнкция и дизъюнкция интерпретируются как последовательное и параллельное соединение соответственно. Однако, не смотря на это, такая логика игр не способна дать средство для описания параллельных процессов. Она позволяет проводить рассуждения об играх безотносительно к порядку их выполнения. Важен лишь факт их выполнения или невыполнения. А значит одновременность выполнения, один из синонимов параллельности, выразить с ее помощью невозможно.
Получается, что нужно иметь средство для описания порядка выполнения игр. Заметим, что порядок выполнения может быть выражен, в частности, средствами временной и динамической логики. Более того, в динамической логике за порядок выполнения отвечает оператор последовательной композиции. Поэтому кажется вполне естественным, на основе анализа его особенностей попытаться построить оператор «параллельной композиции». В результате получится расширение динамической логики игр на параллельную композицию.
В динамической логике игр последовательная композиция а;3 означает, что сначала выполняется игра а, а затем игра (3. Причем выполнение игры а не зависит от выполнения игры (3. В то же время выполнение игры (3 целиком определяется результатом выполнения игры а. Основываясь на этом, можно предположить полную взаимозависимость игр для параллельной композиции а (3. Другими словами, процесс выполнения игры а будет определяться процессом выполнения игры (3, и наоборот. Для того чтобы удовлетворять данному требованию каждая из игр или должна иметь какой-либо дефицит информации, восполняемый в процессе параллельной игры, или допускать модификацию данных как, например, в немонотонной логике. Формально это означает, что каждая из игр, связываемых таким оператором параллельной композиции, должна содержать открытый параметр, получающий значение извне. В противном случае, выполнение этих игр будет независимым, и, следовательно, не требующим одновременности. Более того, средств "булевой логики игр" будет вполне достаточно для их описания.
Для передачи значений открытым параметрам, между параллельными играми должен происходить обмен информацией. Информация передается из обеих игр, и если она востребована одной игрой, то должна быть восполнена другой. Это означает, что передача информации должна быть синхронизирована. Полученная информация может влиять на поведение (выбор) игрока, но главное то, что она влияет на результат. Обмен информацией осуществляется по каналам связи. Они, в свою очередь, как и игры, могут быть параллельными или последовательными. При определении параллельных игр не последнюю роль играет то, какой канал связи используется.
Отношение вынуждения для игр с ограниченной рациональностью
Начальное состояние игры сопоставляется посредством отношения вынуждения с фиксированными наборами финальных состояний. С каждым из игроков сопоставляются свои наборы. И отношение вынуждения и стратегия могут быть напрямую связаны с гарантиями, которые способен дать игрок относительно результата игры еще до ее начала. По-видимому, в играх нет других элементов, кроме стратегии, с которыми можно было бы соотнести отношение вынуждения. Более того, профессор Ван Бентем (см., например, van Benthem, 1999) прямо в определении отношения вынуждения привязывает его к стратегии. Согласно его определению (х, X) є р ,(сс) соответствует тому, что игрок і в игре а из состояния х имеет стратегию, гарантирующую результат в пределах X. Заметим, что и здесь отношение вынуждения замкнуто относительно надмножеств.
Получается, что если для отношения вынуждения условие монотонности выполняется всегда, то для стратегии в случае игр ограниченной рациональностью условие монотонности не выполняется. Подобное расхождение свойств отношения вынуждения и стратегии не существенно для детерминированных конечных игр. Для таких игр предполагается, что игрок знает все стратегии априори. Значит, он сможет идентифицировать нити, дающие финальные состояния отношению вынуждения, но не входящие в стратегию рассматриваемого игрока. В результате, отказавшись от выбора данных нитей в процессе игры, он сможет гарантировать окончание игры в пределах исходной стратегии, т.е. исходного подмножества отношения вынуждения. Однако после того как будет введено ограничение на рациональность игроков, а именно, на их знание о стратегиях, отмеченное здесь различие нужно будет учитывать. Помимо представления игр с помощью экстенсивной формы, используются и другие. В данном разделе рассмотрим стратегическую (или нормальную) форму. Использование этой формы для описания игр привносит свою специфику в определение стратегии. Ниже, после того как будет дано определение стратегии для нормальной формы, проанализируем его отличие от определения стратегии для экстенсивной формы. Кроме того, как и в случае с экстенсивной формой, попробуем сопоставить понятия стратегии и отношения вынуждения.
Стратегическая (нормальная) форма игры задается с помощью таблицы. Заголовки строк этой таблицы содержат наборы действий одного игрока, в то время как заголовки столбцов - наборы действий другого. Каждый из этих наборов является кортежем, т.е. порядок записи действий внутри набора существенен. Для отдельного игрока все наборы действий, представленные в этой таблице, имеют одинаковую длину. Эта длина равняется числу состояний в игре, в которых рассматриваемый игрок делает свой выбор. Для составления наборов нужно перенумеровать все такие состояния. В каждом из этих состояний есть непосредственно выходящие из него действия. Для составления произвольного набора нужно взять по одному такому действию из каждого состояния и подставить его в набор в соответствии с порядковым номером этого состояния. Таким образом, рассматривая все возможные варианты, получим все наборы действий для заголовков таблицы. Каждая из ячеек таблицы сопоставляется с некоторым финальным состоянием, а также с возможным результатом игры, получающимся по достижении этого состояния. Указанное состояние будет достигнуто, если игроки воспользуются действиями, входящими в наборы, записанные в заголовках столбца и строки данной ячейки. Эти наборы и являются стратегиями игры, записанной в нормальной (стратегической) форме.
Для примера рассмотрим преобразование игры, представленной на Рис. 3.2 в виде экстенсивной формы, в стратегическую форму. В результате преобразования получим следующую таблицу.
Если экстенсивная форма соответствует тем играм, для которых игрок может на каждом шаге игры сопоставлять свой текущий выбор с тем, что уже сделано в игре, то стратегическая форма скорее соответствует тем играм, для которых игрок должен еще до начала игры фиксировать (обычно в тайне от соперника) все свои действия.
Стратегия данного игрока, определенная для экстенсивной формы не обязана содержать действия из каждого состояния игры, где этот игрок делает выбор. Своим выбором определенного действия, при построении конкретной стратегии, игрок может отсекать от нее поддеревья, начинающиеся другими действиями, идущими из данного состояния. Стратегии же нормальной формы игры содержат действия из всех состояний игры, в которых данный игрок делает свой выбор. Однако если стратегии экстенсивной формы могут содержать несколько действий непосредственно выходящих из одного состояния, то для нормальной формы в стратегию может входить строго одно такое действие. В некотором смысле в нормальной форме стратегиями называются не только комбинации действий, но и псевдокомбинации действий, которые в процессе одной игры никогда не могут встретиться вместе. Налицо некая избыточность описания. Даже если игрок выбором действия из своей стратегии сужает возможное развитие событий до фиксированного поддерева, он все равно в дальнейшем сохраняет информацию и о других поддеревьях.
Стратегии для нормальной формы игры не могут быть монотонно расширены. Но если в случае стратегий для игр, записанных в экстенсивной форме, монотонное расширение невозможно только для некоторых игр, например, с ограниченной рациональностью, то для стратегий, записанных в нормальной форме, оно не возможно никогда. Рассмотрим стратегию нормальной формы FR: (хо, {хз, ?}) игрока 2 (Таб. 3.8). Она не может быть расширена, к примеру, до (х0, {х3, Xs, j}), т.к. это потребовало бы создания псевдостроки с псевдодействием игрока 1. Разумеется, можно придумывать различные трюки, расширяя определение стратегии на псевдодействия, но в данном случае это кажется не уместным.
В результате мы получили, что по отношению к свойству монотонности стратегия нормальной формы и отношение вынуждения ведут себя по-разному. Помимо этого не понятно как можно задать ограничение рациональности, основываясь на представлении игры в виде нормальной формы.
