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
З.ЗАЯвные и неявные способы описания миров...181
3.4. Параллельные игры с ограниченной рациональностью...184
3.4.1.Игровая форма и модель игры...184
3.4.2. Синтаксис и семантика...187
Заключение...191
Литература...195
Введение1
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы
Логика Хоара была разработана для того, чтобы можно было, избегая тестирования, проверять работоспособность программ и точно описывать выдаваемый результат. Логика Хоара имела ряд недостатков, ограничивающих область ее применения, которые были устранены в динамической логике. В процессе развития вычислительных систем пользователь постепенно стал оказывать все большее и большее влияние на ход выполнения программ. В результате чего потребовался переход к теоретико-игровой семантике. Развитие динамической логики игр, обладающей такой семантикой, может приблизить нас к созданию инструмента для верификации человеко-машинных систем. Подобным многопользовательским системам характерна параллельная обработка информации в условиях ограниченности ресурсов.
Между тем современная логика не имеет достаточных средств, описывающих параллельные системы с ограниченными ресурсами. Большинство логических моделей построено с расчетом на неограниченную рациональность. Эта неограниченность не имеет ничего общего с ответами Оракула, способного, неведомым нам способом, решить любую проблему. Концепция неограниченной рациональности имеет несколько аспектов. Допустим, что человеко-машинная система решает некоторую задачу. Тогда, во-первых, в случае неограниченной рациональности считается, что все участники системы владеют исчерпывающей информацией обо всем, что в ней происходит и находится, или, по крайней мере, существует алгоритм, позволяющий им получить такую информацию. Во-вторых, если эта задача
1 Работа выполнена при поддержке РГНФ, грант № 03-03-00455а
разрешима на машине Тьюринга, то предполагается, что ее решение представлено в описываемой системе, вне зависимости от сложности этой задачи, т.е. затрата материальных и временных ресурсов не учитывается. Саймон (Simon, H.A., 1978) в своей Нобелевской лекции подчеркивал эмпирическую ограниченность таких описаний для теории принятия решений. Совершенно очевидна их ограниченность и для прикладных задач информатики. Например, на данный момент не существует «чудо компьютера», способного просчитать все ходы шахмат. Но поскольку шахматы являются конечной игрой с четко определенными ходами, то в случае использования логики, предполагающей неограниченную рациональность, придется считать, что один из игроков имеет выигрышную стратегию. Однако такой подход видится не очень естественным.
За последние сорок лет представлено множество формализации параллельных процессов в теоретической информатике и теории формальных языков. Существует и математическая модель: алгебра параллельных процессов. К сожалению, в логике эта тема почти не отражена. Этот факт показывает не консервативность логики, а технические трудности представления параллелизма логическими средствами, без нарушения существующих концепций. Помимо того, что новые операторы/связки нужно суметь связать со старыми, с помощью новых операторов нужно попытаться выразить нечто новое, не сводимое к уже известным операторам. Иначе особого смысла нововведения иметь не будут.
Параллелизм в логике представлен в теоретико-игровой интерпретации линейной логики, идеи которой были использованы мной при создании первого расширения динамической логики игр на параллельные операторы. Это расширение позволило выявить некоторые свойства и закономерности, присущие параллельным играм. Оказалось, что, в случае этого расширения,
параллельные операторы не сводимы к непараллельным, только для игр с несовершенной информацией, или подобным им. Была обнаружена и успешно решена проблема кратных миров. К сожалению, параллельные операторы в этом расширении связаны с копирующей стратегией, позволяющей добиваться победы только в двойственных играх. Сама копирующая стратегия кажется несколько искусственной, а область ее применения довольно узкой. Кроме того, такой подход позволяет задавать новые операторы неограниченно, связывая их с новыми стратегиями розыгрыша параллельных игр. При построении новых стратегии могут быть использованы различные основания: структурные особенности игр, соотношение свойств классов игр, и т.п. Для логических систем такие стратегии было бы естественнее связывать с набором предикатов, а не операторами, потому, что логические операторы не должны решать какие-то локальные задачи. Они должны иметь описание, не зависящее от конкретного типа задач. Не смотря на то, что каждая из этих стратегий позволяет построить решение для целого класса игр, обобщения, обосновывающего введение единого, не зависящего от конкретного типа задач, параллельного оператора (или нескольких операторов), с их помощью получить нельзя. Для нахождения общего основания введения параллельных операторов, полезно будет выяснить: почему одну пару игр мы считаем параллельной, а другую нет.
Еще одной системой, описывающей параллельные процессы, является конкурентная динамическая логика. Однако, во-первых, использование теоретико-игровой семантики для этой логики совсем не очевидно, а, во-вторых, способ определения оператора совмещения мне представляется довольно спорным. Он идет вразрез с теоретико-модельной семантикой Крипке, согласно которой, вычислительный процесс не может оказаться одновременно в нескольких мирах. Я вовсе не считаю, что от семантики
Крипке нельзя отклоняться, но, по-моему, это следует делать только в случае крайней необходимости.
Повсеместное распространение сетевых решений, в частности благодаря развитию телефонных коммуникаций и Интернета, поднимают вопрос о гарантиях стабильности работы создаваемых систем. Проверка работоспособности таких систем путем эксплуатации, или тестирования, в течение определенного промежутка времени не способна показать отсутствие ошибок, а лишь позволяет выявлять некоторые из них. Учитывая повсеместное внедрение сетевых решений, следует ожидать, что цена не выявленных ошибок может оказаться огромной.
Исходя из сказанного, анализ аспектов параллелизма, которые могут быть выражены в логике, расширение динамической логики игр на параллельные операторы, и исследование моделей игр с ограниченной рациональностью представляются актуальными.
Степень разработанности темы
В 50е-60е годы XX века появились и теория игр, за вклад в которую Харсани (Harsanyi), Нэш (Nasli) и Селтен (Selteri) в 1993 году получили Нобелевскую премию, и, связанные с ней, математические логические игры (Lorenzen, Ehrenfeucht/Fraisse, Hintikka). В те же годы была предложена и теория ограниченной рациональности, за вклад в которую Леонид Витальевич Канторович в 1975 и Саймон в 1978 году получили Нобелевские премии, и сети Петри (Petri), с помощью которых были выделены основные аспекты распределенных параллельных систем, как концептуально, так и математически.
Модели, позволяющие описывать различные аспекты параллельных процессов, представлены в алгебре параллельных процессов, конкурентной
8
динамической логике (Peleg, D., 1987), теоретико-игровой интерпретации мультипликативной линейной логики (Blass, A., 1992), в различных системах грамматик теории формальных языков, включающих системы Линденмайера, эко грамматики, колонии. В теоретической информатике такими моделями являются сети Петри и я - исчисление. К ним же можно отнести методы эволюционного и генетического программирования.
Впервые теоретико-игровая интерпретация операторов динамической ^ логики была предложена Парихом (Parikh, R., 1985). Впоследствии
динамическая логика игр, вместе с другими логиками игр и логическими играми, активно исследовалась в Университете Амстердама группой, возглавляемой проф. Ван Бентемом (van Benthem, J., 2002В). Разновидности динамической логики игр и их применение отражены в диссертации Марка Паули (Pauly, М., 2001В). Описание игр с ограниченной рациональностью в логике действий изложено в диссертации Хуанга (Huang, Zh., 1994). Первое расширение динамической логики игр на параллельные операторы представлено в моей магистерской диссертации, выполненной в Университете Амстердама (Netchitailov, Iou.V., 2001 А).
Цель и задачи исследования
Главная цель данного диссертационного исследования состоит, во-первых, в выявлении аспектов параллелизма, которые могут быть выражены в логике, и, в частности, в динамической логике игр. Во-вторых, в создании модели ограниченной рациональности, совместимой с языком динамической логики игр, и, в-третьих, в расширении динамической логики игр на параллельные операторы. Для достижения поставленной цели в диссертации решаются следующие задачи:
• раскрываются мотивы использования интенсиональных логик, и исследуются их выразительные возможности
• обосновываются причины введения параллельных операторов и ограниченной рациональности в динамическую логику игр
• анализируются некоторые способы представления параллельных процессов в математике, логике, теории формальных языков и теоретической информатике
• анализируются естественнонаучные корни метафоры параллелизма, и выявляется специфика использования атрибута параллельности в логике
• анализируются существующие теоретико-игровые формы представления игр
• рассматриваются варианты представления игр в динамической логике игр
• анализируются возможные причины дефицита информации и способы их описания в теории игр
Методология исследования
Причины введения параллельных операторов и ограниченной рациональности обосновываются в результате анализа проблем передачи знания. При этом проводится аналогия между гносеологическим подходом к этой проблеме и подходом теоретической информатики. При изучении существующих способов представления параллельных процессов, а так же теоретико-игровых форм используется междисциплинарный сравнительный анализ и метод анализа источников. При создании модели игр с ограниченной рациональностью, на примере шахмат, проводится структурный анализ стратегий, знаний и поведения игроков. При расширении динамической логики игр на параллельные операторы используется принцип «бритвы Оккама».
10
Научная новизна диссертационного исследования
Научная новизна диссертации может быть кратко сформулирована в следующих положениях:
• проанализирована полнота выразительных средств интенсиональных логик, и исследованы их возможности при описании межъязыковых коммуникаций
• предложена мотивация введения параллельных операторов и *' ограниченной рациональности в динамическую логику игр
• проведено междисциплинарное исследование и систематизация опыта описания параллельных процессов
• построена модель динамической логики игр с параллельными операторами: альтернирующая динамическая логика игр
• построена модель игр с ограниченной рациональностью
• выделены возможные причины, по которым игроки могут не достигать целей в играх с ограниченной рациональностью
• определена линейная форма игры, с помощью которой можно представлять игры с ограниченной рациональностью в динамической логике игр
• для динамической логики игр предложен способ представления игр с произвольным положительным числом участников
• построена модель динамической логики игр для параллельных игр с двунаправленной коммуникацией, ограниченной рациональностью и произвольным положительным числом участников
Апробация работы
Некоторые материалы данного исследования изложены в публикации, изданной в научной серии Университета Амстердама, а также были представлены на
И
одном из выступлений в Институте Логики, Языка и Вычислений (Университет Амстердама).
Материалы данного исследования представлялись в виде публикаций тезисов и докладов на следующих конференциях:
• «Третьи Смирновские чтения», Сектор логики Института философии РАН, май 2001;
• «Седьмая Общероссийская Конференция Современная логика: проблемы теории, истории и применения в науке», СПбГУ, Санкт-Петербург, июнь 2002;
• «Международная Научная Конференция: Информация Коммуникация Общество ИКО2002», ЛЭТИ, Санкт-Петербург; ноябрь 2002;
• «Четвертые Смирновские чтения», Сектор логики Института философии РАН май 2003;
• «Международная Научная Конференция: Информация Коммуникация Общество ИКО2003», ЛЭТИ, Санкт-Петербург; ноябрь 2003;
Отдельные положения диссертации использованы автором при проведении серии семинаров «Логика, Игры, Коммуникация» в Санкт-Петербургском Государственном Университете. Диссертационные исследования поддержаны РГНФ: грант на 2003 год. Некоторые материалы данного исследования опубликованы в сборнике «Логические исследования» за 2003 год. Диссертация обсуждена на заседании кафедры логики философского факультета СПбГУ.
Структура и объем диссертации
Диссертация изложена на 200 страницах. Общая структура диссертационного исследования определяется её основной целью и задачами. Текст диссертации содержит введение, три главы, заключение и список литературы из 75 наименований на русском и английском языках.
12
ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении обосновывается актуальность темы исследования, показывается степень ее разработанности, определяются цели и задачи исследования, указывается методология и научная новизна диссертации. Кратко излагается структура и основное содержание диссертации.
В первой главе «Границы развития интенсиональной доктрины» раскрываются мотивы использования интенсиональных логик, рассматриваются их выразительные возможности, сравниваемые с возможностями экстенсиональных логик. На основе анализа проблемы средней формулы, проводится исследование полноты выразительных средств интенсиональных логик. Обосновываются причины введения параллельных операторов и ограниченной рациональности в динамическую логику игр, и очерчивается круг проблем, описываемых с их помощью.
В первом разделе первой главы «Проблемы и парадоксы экстенсиональной логики» раскрывается один из мотивов использования интенсиональных логик. Он связан с парадоксами, возникающими при интерпретации интенсиональных контекстов средствами экстенсиональных логик. Эти парадоксы «естественным образом» устраняются при переходе к интенсиональным логикам. Данный переход стал возможным благодаря семантике Крипке, позволившей совершить революционный шаг в развитии интенсиональных логик. Демонстрация важности интенсиональных логик опирается на тезис о том, что интенсиональные контексты невозможно полностью исключить из научного языка (антитезис экстенсиональности).
Для выполнения данных рассуждений, анализируется различие и особенности экстенсионального и интенсионального подходов в логике. Поскольку экстенсиональные и интенсиональные логики относятся к классу
13
формализованных языков, предварительно описывается структура этого класса. В формализованном языке выделяются формальная и семантическая составляющие. Обсуждаются правила семантической интерпретации. Рассматриваются способы их связи с формальными системами.
В рамках данной диссертационной работы проводится междисциплинарное исследование опыта описания параллельных процессов. Базовые определения формальных систем, в той или иной мере, отличаются в логике, математике, теории формальных языков и теоретической информатике. Между тем, они столь элементарны, что специалист, при переходе из одной области в другую может даже не задуматься о возможном различии, что естественно может привести к неверным интерпретациям. Поэтому, в данном разделе, представляется целесообразным рассмотрение основ теории формальных систем и сравнительный анализ их использования в указанных дисциплинах.
Во втором разделе первой главы «От описания корректности работы программ к описанию работы недетерминированных систем» приводится еще один мотив использования интенсиональных логик: на их основе можно попытаться разработать эффективное средство для верификации программ, избегая метод «слепого» тестирования. Помимо того, что данный пример интересен сам по себе, он может быть полезен в том случае если кому-то вдруг удастся доказать тезис экстенсиональности, или же кто-то просто не согласен с антитезисом экстенсиональности. В таком случае, мотивация, изложенная в предыдущем разделе, может быть «запятнана». В результате, данный пример выступит и в роли «спасательного круга».
Исторически, первым примером логической системы, предназначенной для верификации программ, является логика Хоара. Как известно, слепое тестирование, затрачивая огромные временные ресурсы, не способно
14
V
доказывать корректность программ. Оно способно лишь «слепо натыкаться» на ошибки, и, таким образом, выявлять некорректность программ.
При декомпозиции, в структуре почти всех сложных программ можно выявить последовательно исполняющиеся блоки. В виде программного кода эти блоки выглядят независимо, оттого и выделяются в качестве блоков, однако в процессе вычисления они связываются между собой передаваемыми основными и промежуточными данными. На входе и выходе сложной программы могут ? определяться одни данные, тогда как на промежуточных входах и выходах
блоков они обычно дополняются данными, являющимися вспомогательными.
Ключевой идеей логики Хоара, позволяющей избежать «слепого» тестирования, является идея использования свойства-инварианта по отношению ко всем блокам рассматриваемой программы, т.е. свойства, которое будучи заданным на входе каждого блока, сохраняется и на выходе. Инвариантные свойства и промежуточные данные в логике Хоара записываются на языке предикатов первого порядка.
В таком случае за один программный цикл можно доказать, вычисляет ли данная программа некоторое свойство. Для этого нужно проверить инвариантность этого свойства по отношению к блокам в процессе выполнения программы. То есть инвариантность этого свойства не должна рассматриваться изолированно для каждого блока. При переходе от блока к блоку не следует терять и промежуточные данные. К сожалению, с прикладной точки зрения, логика Хоара оказалась не эффективной в силу отсутствия алгоритма получения свойства-инварианта для данной программы, или получения программы, сохраняющей данное свойство.
Помимо этого, логика Хоара имеет свойство, делающее ее неполной. Не смотря на то, что промежуточные данные, передаваемые между двумя последовательными блоками программы, должны существовать всегда, они
15
V
могут оказаться невыразимыми на языке предикатов первого порядка. Подобного рода проблемы можно классифицировать как проблемы невыразимости средней формулы. Периодически возникающие проблемы невыразимости способствовали развитию логических систем.
Возникновение данной проблемы в логике Хоара мне видится результатом того, что или язык, на котором пишутся программы, выходит за пределы первопорядковой логики, или же связь между элементами программы ** (ветвление, параллелизм) не представимы на языке этой логики.
Пратт решил проблему невыразимости средней формулы, присутствовавшую в логике Хоара, расширением языка логики первого порядка, посредством программной модальности, до языка динамической логики.
В процессе развития вычислительных систем пользователь постепенно стал оказывать все большее и большее влияние на ход выполнения программ. Появился термин: человеко-машинная система. Если пытаться описывать такие системы средствами динамической логики, то снова возникнет проблема невыразимости средней формулы. Для ее устранения нужно перейти к теоретико-игровой семантике. В результате чего понятие процесса будет
заменено понятием игры. То, что называется игрой в логике игр и теории игр
т
является абстрактным математическим объектом. Причиной создания таких
объектов стала потребность моделирования процессов, ход выполнения которых не однозначен и зависит от внешнего, алгоритмически не заданного вмешательства.
Таким образом, на проблему неустранимости средней формулы можно взглянуть как на одну из причин эволюции интенсиональной логики от логики Хоара к динамической логике игр.
16
В третьем разделе первой главы «Язык как средний терм при переносе информации» продолжено исследование выразительных возможностей интенсиональных логик и полноты их выразительных средств. Проанализированы их возможности в описании межъязыковых коммуникаций. Предложена мотивация введения параллельных операторов и ограниченной рациональности в динамическую логику игр, и очерчена область проблем, на решение которых подобная логика может быть направлена.
В ходе исследования в данном разделе проводится аналогия между гносеологическим подходом к проблеме передачи знания и подходом теоретической информатики. Выполняется сравнительный анализ этих подходов, позволяющий добиться некоторой ясности в данном вопросе.
Вначале выделяются объектная и операционная семантики. Язык программ высокого уровня обладает объектной семантикой, соответствующей обычной теоретико-модельной семантике формализованных языков. Такие программы апеллируют к абстрактным математическим объектам, возможно функциям. Язык машинных кодов обладает операционной семантикой, являющейся представлением того, что происходит внутри компьютера, когда выполняется откомпилированная программа. Аналогично двумя способами можно рассматривать и естественный язык: с одной стороны, в терминах некоторой теории смысла, и, с другой стороны, связывать язык с поведением.
Операционная семантика не фиксирует объектной семантики. Мы знаем, что делает программа, но мы просто не уверены, как точно интерпретировать ее поведение. В результате мы получим точный компьютерный аналог знаменитого тезиса неопределенности Куайна. Как представлял Куайн, антрополог, высадившийся на далеком острове, будет иметь огромную проблему при составлении разговорника доселе неизвестного языка, на основе наблюдаемых высказываний аборигенов. Проблема "радикального перевода"
17