автореферат диссертации по философии, специальность ВАК РФ 09.00.07
диссертация на тему: Проблема формализации концепций параллелизма и ограниченной рациональности средствами динамической логики игр
- Год: 2003
- Автор научной работы: Нечитайлов, Юрий Вячеславович
- Ученая cтепень: кандидата философских наук
- Место защиты диссертации: Санкт-Петербург
- Код cпециальности ВАК: 09.00.07
Полный текст автореферата диссертации по теме "Проблема формализации концепций параллелизма и ограниченной рациональности средствами динамической логики игр"
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
Проблема формализации концепций параллелизма и ограниченной рациональности средствами динамической логики игр
Специальность 09.00.07 - логика
АВТОРЕФЕРАТ
диссертации на соискание ученой степени кандидата философских наук
На правах рукописи
НЕЧИТАЙЛОВ Юрий Вячеславович
Санкт-Петербург
2003
Работа выполнена на кафедре логики философского факультета Санкт-Петербургского государственного университета
Научный руководитель:
доктор философских наук, профессор Слинин Ярослав Анатольевич Официальные оппоненты:
доктор философских наук, профессор Караваев Эдуард Федорович кандидат философских наук Милославов Алексей Сергеевич
Ведущая организация:
Сектор логики Института философии РАН
диссертационного совета Д.212.232.03 по защите диссертаций на соискание ученой степени доктора философских наук при Санкт-Петербургском государственном университете по адресу: 199034, СанктД1етербург, В.О., Менделевская линия, д. 5, Философский факультет, ауд. 10
С диссертацией можно ознакомиться в научной библиотеке им. М. Горького Санкт-Петербургского государственного университета
Защита состоится 22 январи 2004 года в
часов на заседании
Автореферат разослан
2003 г.
Ученый секретарь Диссертационного совета, кандидат философских наук, доцент
Г.П. Любимов
2004-4 3
17911 J
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ1
Актуальность темы
Логика Хоара была разработана для того, чтобы можно было, избегая тестирования, проверять работоспособность программ и точно описывать выдаваемый результат. Логика Хоара имела ряд недостатков, ограничивающих область ее применения, которые были устранены в динамической логике. В процессе развития вычислительных систем пользователь постепенно стал оказывать все большее и большее влияние на ход выполнения программ. В результате чего потребовался переход к теоретико-игровой семантике. Развитие динамической логики игр, обладающей такой семантикой, может приблизить нас к созданию инструмента для верификации человеко-машинных систем. Подобным многопользовательским системам характерна параллельная обработка информации в условиях ограниченности ресурсов.
Между тем современная логика не имеет достаточных средств, описывающих параллельные системы с ограниченными ресурсами. Большинство логических моделей построено с расчетом на неограниченную рациональность. Эта неограниченность не имеет ничего общего с ответами Оракула, способного, неведомым нам способом, решить любую проблему. Концепция неограниченной рациональности имеет несколько аспектов. Допустим, что человеко-машинная система решает некоторую задачу. Тогда, во-первых, в случае неограниченной рациональности считается, что все участники системы владеют исчерпывающей информацией обо всем, что в ней происходит и находится, или, по крайней мере, существует алгоритм, позволяющий им получить такую информацию. Во-вторых, если эта задача
1 Работа выполнена при поддержке РГНФ, грант № 03-03-00455^ 1IА ЦНОНАЛЬМАЯ |
| библиотека I I СПепИвг 1 * • О» I
/
разрешима на машине Тьюринга, то предполагается, что ее решение представлено в описываемой системе, вне зависимости от сложности этой задачи, т е затрата материальных и временных ресурсов не учитывается. Саймон в своей Нобелевской лекции подчеркивал эмпирическую ограниченность таких описаний для теории принятия решений.2 Совершенно очевидна их ограниченность и для прикладных задач информатики Например, на данный момент не существует «чудо компьютера», способного просчитать все ходы шахмат. Но поскольку шахматы являются конечной игрой с четко определенными ходами, то в случае использования логики, предполагающей неограниченную рациональность, придется считать, что один из игроков имеет выигрышную стратегию. Однако такой подход видится не очень естественным.
За последние сорок лет представлено множество формализации параллельных процессов в теоретической информатике и теории формальных языков. Существует и математическая модель: алгебра параллельных процессов К сожалению, в логике эта тема почти не отражена. Этот факт показывает не консервативность логики, а технические трудности представления параллелизма логическими средствами, без нарушения существующих концепций. Помимо того, что новые операторы/связки нужно суметь связать со старыми, с помощью новых операторов нужно попытаться выразить нечто новое, не сводимое к уже известным операторам. Иначе особого смысла нововведения иметь не будут.
Параллелизм в логике представлен в теоретико-игровой интерпретации линейной логики, идеи которой были использованы мной при создании первого расширения динамической логики игр на параллельные операторы. Это расширение позволило выявить некоторые свойства и закономерности,
" Simim, H А., 1978, "Rational Decision-making in Business' Organisations" Nobel Memorial LecUire, 8 Decemder, 1978
y ,4«
» 1 . " -
ал
присущие параллельным играм. Оказалось, что, в случае этого расширения, параллельные операторы не сводимы к непараллельным, только для игр с несовершенной информацией, или подобным им. Была обнаружена и успешно решена проблема кратных миров. К сожалению, параллельные операторы в этом расширении связаны с копирующей стратегией, позволяющей добиваться победы только в двойственных играх. Сама копирующая стратегия кажется несколько искусственной, а область ее применения довольно узкой. Кроме того, такой подход позволяет задавать новые операторы неограниченно, связывая их с новыми стратегиями розыгрыша параллельных игр. При построении новых стратегии могут быть использованы различные основания: структурные особенности игр, соотношение свойств классов игр, и т.п. Для логических систем такие стратегии было бы естественнее связывать с набором предикатов, а не операторами, потому, что логические операторы не должны решать какие-то локальные задачи. Они должны иметь описание, не зависящее от конкретного типа задач. Не смотря на то, что каждая из этих стратегий позволяет построить решение для целого класса игр, обобщения, обосновывающего введение единого, не зависящего от конкретного типа задач, параллельного оператора (или нескольких операторов), с их помощью получить нельзя. Для нахождения общего основания введения параллельных операторов, полезно будет выяснить: почему одну пару игр мы считаем параллельной, а другую нет.
Еще одной системой, описывающей параллельные процессы, является конкурентная динамическая логика. Однако, во-первых, использование теоретико-игровой семантики для этой логики совсем не очевидно, а, во-вторых, способ определения оператора совмещения мне представляется довольно спорным. Он идет вразрез с теоретико-модельной семантикой Крипке, согласно которой, вычислительный процесс не может оказаться одновременно в нескольких мирах. Я вовсе не считаю, что от семантики
Крипке нельзя отклоняться, но, по-моему, это следует делать только в случае крайней необходимости.
Повсеместное распространение сетевых решений, в частности благодаря развитию телефонных коммуникаций и Интернета, поднимают вопрос о гарантиях стабильности работы создаваемых систем. Проверка работоспособности таких систем путем эксплуатации, или тестирования, в течение определенного промежутка времени не способна показать отсутствие ошибок, а лишь позволяет выявлять некоторые из них. Учитывая повсеместное внедрение сетевых решений, следует ожидать, что цена не выявленных ошибок может оказаться огромной.
Исходя из сказанного, анализ аспектов параллелизма, которые могут быть выражены в логике, расширение динамической логики игр на параллельные операторы, и исследование моделей игр с ограниченной рациональностью представляются актуальными.
Степень разработанности темы
В ЗСУ'-бО0 годы XX века появились и теория игр, за вклад в которую Харсани (Harsanyi), Нэш (Nash) и Селтен (Selten) в 1993 году получили Нобелевскую премию, и, связанные с ней, математические логические игры (Lorenzen, Ehrenfeucht/Frai'sse, Hintikka). В те же годы была предложена и теория ограниченной рациональности, за вклад в которую Леонид Витальевич Канторович в 1975 и Саймон в 1978 году получили Нобелевские премии, и сети Петри (Petri), с помощью которых были выделены основные аспекты распределенных параллельных систем, как концептуально, так и математически.
Модели, позволяющие описывать различные аспекты параллельных процессов, представлены в алгебре параллельных процессов, конкурентной
динамической логике,3 теоретико-игровой интерпретации мультипликативной линейной логики,4 в различных системах грамматик теории формальных языков, включающих системы Линденмайера, эко грамматики, колонии. В теоретической информатике такими моделями являются сети Петри и я - исчисление. К ним же можно отнести методы эволюционного и генетического программирования.
Впервые теоретико-игровая интерпретация операторов динамической логики была предложена Парихом в 1985 году.5 Впоследствии динамическая логика игр, вместе с другими логиками игр и логическими играми, активно исследовалась в Университете Амстердама группой, возглавляемой проф. Ван Бентемом.6 Разновидности динамической логики игр и их применение отражены в диссертации Марка Паули.7 Описание игр с ограниченной рациональностью в логике действий изложено в диссертации Хуанга.8 Первое расширение динамической логики игр на параллельные операторы
3 Peleg, £>., 1987, "Concurrent Dynamic Logic" Journal of the Association for Computing Machinery, Volume 34, Nomber 2, 450-479
4 Blass, A., 1992, "A Game Semantics for Linear Logic " Annals of Pure and Applied Logic, Volume 56, 183-220
Abramsky, S., Jagadeesan, R., 1994, "Games and Full Completeness for Multiplicative Linear Logic" The Journal of Symbolic Logic, Volume 59, Number 2, 543-574
5Pankh, R., 1985, "The Logic of Games and it.s Applications "Annals of Discrete Mathematics, 24, Elsevier, 111-139
6van Benthem, J, 2002, "What Logic Games are Trying to Tell Us" R.Downey, ed., Proceedings of
7dl and 8'11 Asian Logic Conferences, World Scientific Press, Singapore.
7 Pauly, M., 2001, "Logicfor Social Software" ILLC Dissertation Series 2001-10, University of Amsterdam, The Netherlands.
8 Huang, Zh., 1994, "Logics for Agents with Bounded Rationality" ILLC Dissertation Series 1994-
10, University of Amsterdam, The Netherlands.
представлено в моей магистерской диссертации, выполненной в Университете Амстердама.9
Цель и задачи исследования
Главная цель данного диссертационного исследования состоит, во-первых, в выявлении аспектов параллелизма, которые могут быть выражены в логике, и, в частности, в динамической логике игр. Во-вторых, в создании модели ограниченной рациональности, совместимой с языком динамической логики игр, и, в-третьих, в расширении динамической логики игр на параллельные операторы. Для достижения поставленной цели в диссертации решаются следующие задачи:
•раскрываются мотивы использования интенсиональных логик, и исследуются их выразительные возможности
• обосновываются причины введения параллельных операторов и ограниченной рациональности в динамическую логику игр
• анализируются некоторые способы представления параллельных процессов в математике, логике, теории формальных языков и теоретической информатике
• анализируются естественнонаучные корни метафоры параллелизма, и выявляется специфика использования атрибута параллельности в логике
• анализируются существующие теоретико-игровые формы представления игр
• рассматриваются варианты представления игр в динамической логике игр
• анализируются возможные причины дефицита информации и способы их описания в теории игр
4 Netihitailov, ton V, 2001, "An Extension of Game U>gic with Parallel Operators" ILLC
Scientific Publications, MoL-2001-02, University of Amsterdam, The Netherlands
Методология исследования
Причины введения параллельных операторов и ограниченной рациональности обосновываются в результате анализа проблем передачи знания. При этом проводится аналогия между гносеологическим подходом к этой проблеме и подходом теоретической информатики. При изучении существующих способов представления параллельных процессов, а так же теоретико-игровых форм используется междисциплинарный сравнительный анализ и метод анализа источников. При создании модели игр с ограниченной рациональностью, на примере шахмат, проводится структурный анализ стратегий, знаний и поведения игроков. При расширении динамической логики игр на параллельные операторы используется принцип «бритвы Оккама».
Научная новизна диссертационного исследования
Научная новизна диссертации может быть кратко сформулирована в следующих положениях:
•проанализирована полнота выразительных средств интенсиональных логик, и исследованы их возможности при описании межъязыковых коммуникаций
• предложена мотивация введения параллельных операторов и ограниченной рациональности в динамическую лог ику игр
• проведено междисциплинарное исследование и систематизация опыта описания параллельных процессов
• построена модель динамической логики игр с параллельными операторами: альтернирующая динамическая логика игр
• построена модель игр с ограниченной рациональностью
• выделены возможные причины, по которым игроки могут не достигать целей в играх с ограниченной рациональностью
• определена линейная форма игры, с помощью которой можно представлять игры с ограниченной рациональностью в динамической логике игр
•для динамической логики игр предложен способ представления игр с произвольным положительным числом участников
•построена модель динамической логики игр для параллельных игр с двунаправленной коммуникацией, ограниченной рациональностью и произвольным положительным числом участников
Положения, выносимые на защиту
1) Проблема «средней формулы», описывающей общее состояние системы при декомпозиции сложных процессов является неустранимой, т.с для любой формальной системы существует модель, для которой, несмотря на то, что средняя формула существует, она является невыразимой на языке этой формальной системы
2) Между процессом приобретения языковых навыков ребенком, и процессом приобретения языковых навыков антропологом при изучении языка аборигенов, имеется существенная разница. Главное отличие в том, что первый процесс можно считать скорее биолого-лингвистическим, в то время как второй - скорее формально-лингвистическим.
3) Объектная и операционная семантики взаимообусловлены, и, в структуре языка, не могут существовать друг без друга. Без операционной семантики не будет инструмента, позволяющего сделать первый шаг для наполнения объектной семантики. Отказ от объектной семантики приведет к тому, что, или нечего будет наполнять, или операционная семантика сама станет объектной.
4) С точки зрения описания процесса передачи знания, динамическая логика игр с параллельными операторами и ограниченной рациональностью полезна для формализации и исследования проблем формально-лингвистической коммуникации.
5) В формальных системах понятие параллелизма, в одних случаях, используется для описания полностью независимых процессов, в других случаях, напротив, для описания взаимозависимых процессов с непосредственной или опосредованной связью. Параллельные операторы в логике имеет смысл вводить только для взаимозависимых игр. Включение описания для полностью независимых параллельных игр потребует принципиального изменения семантики Крипке.
6) Для динамической логики игр с ограниченной рациональностью отношение вынуждения должно быть немонотонным, в отличие от динамической логики игр с неограниченной рациональностью.
7) Понятие квазивыигрышной стратегии очерчивает класс игр с ограниченной рациональностью, для которых построена модель динамической логики игр для параллельных игр с двунаправленной коммуникацией, ограниченной рациональностью и произвольным положительным числом участников
Теоретическое и практическое значение диссертации
Результаты, полученные в данной диссертации, могут быть использованы для описания параллельных процессов с двунаправленной коммуникацией ограниченной рациональностью и неограниченным положительным числом участников. Это может помочь приблизиться к формализации процесса передачи знания, в процессе формально-лингвистической коммуникации. Кроме того, результаты могут быть использованы для дальнейших
исследований игр с ограниченной рациональностью, а также для поиска описания логическими средствами других классов параллельных игр. Материал диссертации может быть использован при создании учебных курсов.
Апробация работы
Некоторые материалы данного исследования изложены в публикации, изданной в научной серии Университета Амстердама, а также были представлены на одном из выступлений в Институте Логики, Языка и Вычислений (Университет Амстердама).
Материалы данного исследования представлялись в виде публикаций тезисов и докладов на следующих конференциях:
• «Третьи Смирновские чтения», Сектор логики Института философии РАН, май 2001;
• «Седьмая Общероссийская Конференция Современная логика: проблемы теории, истории и применения в науке», СПбГУ, Санкт-Петербург, июнь 2002;
• «Международная Научная Конференция: Информация Коммуникация Общество ИК02002», ЛЭТИ, Санкт-Петербург; ноябрь 2002;
• «Четвертые Смирновские ч гения», Сектор логики Института философии РАН май 2003;
• «Международная Научная Конференция: Информация Коммуникация Общество ИК02003», ЛЭТИ, Санкт-Петербург; ноябрь 2003;
Отдельные положения диссертации использованы автором при проведении серии семинаров «Логика, Игры, Коммуникация» в Санкт-Петербургском Государственном Университете. Диссертационные исследования поддержаны РГНФ: грант на 2003 год. Некоторые материалы данного исследования
опубликованы в сборнике «Логические исследования» за 2003 год. Диссертация обсуждена на заседании кафедры логики философского факультета СПбГУ
Структура и объем диссертации
Диссертация изложена на 200 страницах. Общая структура диссертационного исследования определяется её основной целью и задачами. Текст диссертации содержит введение, три главы, заключение и список литературы из 75 наименований на русском и английском языках
ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении обосновывается актуальность темы исследования, показывается степень ее разработанности, определяются цели и задачи исследования, указывается методология и научная новизна диссертации. Кратко излагается структура и основное содержание диссертации.
В первой главе «Границы развития интенсиональной доктрины» раскрываются мотивы использования интенсиональных логик, рассматриваются их выразительные возможности, сравниваемые с возможностями экстенсиональных логик. На основе анализа проблемы средней формулы, проводится исследование полноты выразительных средств интенсиональных логик. Обосновываются причины введения параллельных операторов и ограниченной рациональности в динамическую логику игр, и очерчивается круг проблем, описываемых с их помощью.
В первом разделе первой главы «Проблемы и парадоксы экстенсиональной логики» раскрывается один из мотивов использования интенсиональных логик. Он связан с парадоксами, возникающими при интерпретации интенсийнальных
котттекстов средствами экстенсиональных логик. Эти парадоксы «естественным образом» устраняются при переходе к интенсиональным логикам Данный переход стал возможным благодаря семантике Крипке, позволившей совершить революционный шаг в развитии интенсиональных логик. Демонстрация важности интенсиональных логик опирается на тезис о том, что интенсиональные контексты невозможно полностью исключить из научного языка (антитезис экстенсиональности).
Для выполнения данных рассуждений, анализируется различие и особенности экстенсионального и интенсионального подходов в логике. Поскольку экстенсиональные и интенсиональные логики относятся к классу формализованных языков, предварительно описывается структура этого класса. В формализованном языке выделяются формальная и семантическая составляющие Обсуждаются правила семантической интерпретации. Рассматриваются способы их связи с формальными'системами.
В рамках данной диссертационной работы проводится междисциплинарное исследование опыта описания параллельных процессов. Базовые определения формальных систем, в той или иной мере, отличаются в логике, математике, теории формальных языков и теоретической информатике. Между тем, они столь элементарны, что специалист, при переходе из одной области в другую может даже не задуматься о возможном различии, что естественно может привести к неверным интерпретациям. Поэтому, в данном разделе, представляется целесообразным рассмотрение основ теории формальных систем и сравнительный анализ их использования в указанных дисциплинах.
Во втором разделе первой главы «От описания корректности работы программ к описанию работы недетерминированных систем» приводится еще один мотив использования интенсиональных логик: на их основе можно
попытаться разработать эффективное средство для верификации программ, избегая метод «слепого» тестирования. Помимо того, что данный пример интересен сам по себе, он может бьггь полезен в том случае если кому-то вдруг удастся доказать тезис экстенсиональности, или же кто-то просто не согласен с антитезисом экстенсиональности. В таком случае, мотивация, изложенная в предыдущем разделе, может быть «запятнана». В результате, данный пример выступит и в роли «спасательного круга».
Исторически, первым примером логической системы, предназначенной для верификации программ, является логика Хоара. Как известно, слепое тестирование, затрачивая огромные временные ресурсы, не способно доказывать корректность программ. Оно способно лишь «слепо натыкаться» на ошибки, и, таким образом, выявлять некорректность программ.
При декомпозиции, в структуре почти всех сложных программ можно выявить последовательно исполняющиеся блоки. В виде программного кода эти блоки выглядят независимо, оттого и выделяются в качестве блоков, однако в процессе вычисления они связываются между собой передаваемыми основными и промежуточными данными. На входе и выходе сложной программы могут определяться одни данные, тогда как на промежуточных входах и выходах блоков они обычно дополняются данными, являющимися вспомогательными.
Ключевой идеей логики Хоара, позволяющей избежать «слепого» тестирования, является идея использования свойства-инварианта по отношению ко всем блокам рассматриваемой программы, т.е. свойства, которое будучи заданным на входе каждого блока, сохраняется и на выходе. Инвариантные свойства и промежуточные данные в логике Хоара записываются на языке предикатов первого порядка.
В таком случае за один программный цикл можно доказать, вычисляет ли данная программа некоторое свойство. Для этого нужно проверить инвариантность этого свойства по отношению к блокам в процессе выполнения
программы. То есть инвариантность этого свойства не должна рассматриваться изолированно для каждого блока. При переходе от блока к блоку не следует терять и промежуточные данные. К сожалению, с прикладной точки зрения, логика Хоара оказалась не эффективной в силу отсутствия алгоритма получения свойства-инварианта для данной программы, или получения программы, сохраняющей данное свойство.
Помимо этого, логика Хоара имеет свойство, делающее ее неполной. Не смотря на то, что промежуточные данные, передаваемые между двумя последовательными блоками программы, должны существовать всегда, они могут оказаться невыразимыми на языке предикатов первого порядка. Подобного рода проблемы можно классифицировать как проблемы невыразимости средней форму аы. Периодически возникающие проблемы невыразимости способствовали развитию логических систем.
Возникновение данной проблемы в логике Хоара мне видится результатом того, что или язык, на котором пишутся программы, выходит за пределы первопорядковой логики, или же связь между элементами программы (ветвление, параллелизм) не представимы на языке этой логики.
Пратт решил проблему невыразимости средней формулы, присутствовавшую в логике Хоара, расширением языка логики первого порядка, посредством программной модальности, до языка динамической логики.
В процессе развития вычислительных систем пользователь постепенно стал оказывать все большее и большее влияние на ход выполнения программ. Появился термин: человеко-машинная система. Если пытаться описывать такие системы средствами динамической логики, то снова возникнет проблема невыразимости средней формулы. Для ее устранения нужно перейти к теоретико-игровой семантике. В результате чего понятие процесса будет заменено понятием игры. То, что называется игрой в логике игр и теории игр
является абстрактным математическим объектом. Причиной создания таких объектов стала потребность моделирования процессов, ход выполнения которых не однозначен и зависит от внешнего, алгоритмически не заданного вмешательства.
Таким образом, на проблему неустранимости средней формулы можно взглянуть как на одну из причин эволюции интенсиональной логики от логики Хоара к динамической логике игр.
В третьем разделе первой главы «Язык как средний терм при переносе информации» продолжено исследование выразительных возможностей интенсиональных логик и полноты их выразительных средств. Проанализированы их возможности в описании межъязыковых коммуникаций. Предложена мотивация введения параллельных операторов и ограниченной рациональности в динамическую логику игр, и очерчена область проблем, на решение которых подобная логика может быть направлена.
В ходе исследования в данном разделе проводится аналогия между гносеологическим подходом к проблеме передачи знания и подходом теоретической информатики. Выполняется сравнительный анализ этих подходов, позволяющий добиться некоторой ясности в данном вопросе.
Вначале выделяются объектная и операционная семантики. Язык программ высокого уровня обладает объектной семантикой, соответствующей обычной теоретико-модельной семантике формализованных языков. Такие программы апеллируют к абстрактным математическим объектам, возможно функциям. Язык машинных кодов обладает операционной семантикой, являющейся представлением того, что происходит внутри компьютера, когда выполняется откомпилированная программа. Аналогично двумя способами можно рассматривать и естественный язык: с одной стороны, в терминах некоторой теории смысла, и, с другой стороны, связывать язык с поведением.
Операционная семантика не фиксирует объектной семантики. Мы знаем, что делает программа, но мы просто не уверены, как точно интерпретировать ее поведение. В результате мы получим точный компьютерный аналог знаменитого тезиса неопределенности Куайна. Как представлял Куайн, антрополог, высадившийся на далеком острове, будет иметь огромную проблему при составлении разговорника доселе неизвестного языка, на основе наблюдаемых высказываний аборигенов. Проблема "радикального перевода" исключительно посредством наблюдения столкнется с теми же трудностями, что и попытка интерпретации некоторой программы только посредством наблюдения за работой ее откомпилированной версии.
В процессе исследования выделено свойство объектной семантики: неоднозначность объектной семантики останется независимо от того, сколько нам известно об операционной семантике.
Благодаря этому, на примере процесса передачи знания, можно построить модель, которая доказывала бы следующее утверждение: для любой формальной системы существует модель, для которой, несмотря на то, что средняя формула существует, она является невыразимой на языке этой формальной системы. То есть, из-за неустранимости проблемы средней формулы, проблемы естественного языка невозможно «окончательно» сформулировать ни в одной формальной системе.
Характер того, каким образом абориген, будучи ребенком, получил связь своей объектной и операционной семантики (т.е. приобрел языковые навыки), и характер того, каким образом эту связь пытается получить антрополог, по-видимому, существенно отличается. Главное отличие в том, что первый процесс можно считать скорее биолого-лингвистическим, в то время как второй - скорее формально-лингвистическим. Этим можно попытаться объяснить, почему антропологу не удается формально фиксировать объектную семантику с помощью операционной, в то время как абориген никаких трудностей
употребления языка не испытывает. То есть здесь дело не в том, что операционная семантика, в принципе, не фиксирует объектной семантики, а в том, что их связь не является формальной.
Более того, объектная и операционная семантики взаимообусловлены, и, в структуре языка, не могут существовать друг без друга. Без операционной семантики не будет инструмента, позволяющего сделать первый шаг для наполнения объектной семантики. Отказ от объектной семантики приведет к тому, что, или нечего будет наполнять, или операционная семантика сама станет объектной. Похоже, что младенцы, вначале усваивают операциошую семантику, в процессе контекстуальной ориентации, и лишь, затем, ребенок начинает опираться на приобретенную операционную семантику, как на объект, в результате чего, получает объектную семантику.
В пользу того, что ребенок не приобретает языковые навыки формально-лингвистическими методами можно высказать множество аргументов. Во-первых, младенец изначально не владеет ни объектной, ни операционной семантикой. Во-вторых, формальным методам ребенка, обычно, никто не учит, он просто погружается в языковую среду. В-третьих, эта языковая среда столь нетривиальна, что до сих пор не поддается даже приближенным формальном описаниям. В-четвертых, даже взрослый, четко знающий формальные методьт, тратит на изучение языка много лет, и, все равно, не достигает того, чего, ребенок способен достичь в первые пять-семь лет своей жизни. И самое главное, ребенок способен получить свои первые языковые навыки лишь до определенного возраста, связанного, скорее всего, с развитием головного мозга, после которого дети не получившие таких навыков утрачивают способность к их приобретению.
Данный вывод согласуется с выводом Серля о том, что человеческие ментальные процессы, в общем, и в языке, в частности, не могут быть сведены лишь к вычислениям и поведению. Поведение, и, в частности, "вычисления"
человеческого мозга порождены самой природой мозга. Компьютерные же программы не являются результатом эволюции самих компьютеров, а установлены искусственно и не зависят от того, на чем им предстоит быть реализованными.
При формализации процесса изучения языка и исследовании проблем формально-лингвистической коммуникации, согласившись с неустранимостью проблемы средней формулы, можно обратиться к поиску оптимального соответствия сопоставляемых языков. Для этого полезно использовать динамическую логику игр с параллельными операторами и ограниченной рациональностью, позволяющую, благодаря семантике Крипке, описывать динамику процессов, и статичность фиксированных для описания моментов реальности.
Во второй главе «Подходы к описанию параллельных процессов и игр» проводится междисциплинарное исследование и систематизация опыта описания параллельных процессов, анализируются естественнонаучные корни метафоры параллелизма, и выявляется специфика использования атрибута параллельности в логике. Представляется модель динамической логики игр с параллельными операторами: альтернирующая динамическая логика игр.
В первом разделе второй главы «Опыт описания параллельных процессов» анализируются некоторые способы представления параллельных процессов в математике, логике, теории формальных языков и теоретической информатике
В рассмотренных формальных системах понятие параллелизма, в одних случаях, используется для описания полностью независимых процессов/игр, в других случаях, напротив, для описания взаимозависимых процессов с непосредственной или опосредованной связью. К процессам с непосредственной связью относят процессы, взаимодействующие внутри сети, с целью перестройки своей структуры, а также с целью корректировки, или
достраивания путей решения проблем. К процессам с опосредованной связью относят процессы, использующие общую среду обитания, общие ресурсы: решение проблем с помощью распределенных систем, конференции с удаленным доступом, экологические системы.
Благодаря анализу конкурентной динамической логики получено, что описание полностью независимых параллельных игр средствами логики, потребует принципиального изменения семантики Крипке
Во втором разделе второй главы «Смысл параллелизма для логики» анализируются естественнонаучные корни метафоры параллелизма, выявляются аспекты параллелизма, которые могли бы быть описаны с помощью логического аппарата, предъявляются требования к параллельным шрам.
Атрибут параллельности, для процессов, обычно употребляется как синоним одновременности. При этом ему противопоставляется последовательность. Заметим, что для четырехмерного многообразия в теории относительности понятие одновременности теряет смысл точно так же как понятие параллельности при его расширении на четырехмерные процессы, а именно, оказывается неопределенным понятием.10
Логика игр благодаря использованию теоретико-игровой семантики имеет свою специфику применения атрибута параллельности. Электрические цепи (релейно-контакгные схемы) служат одной из моделей операторов булевой алгебры. В частности конъюнкция и дизъюнкция интерпретируются как последовательное и параллельное соединение соответственно. Однако, не смотря на это, такая логика игр не способна дать средство для описания параллельных процессов. Она позволяет проводить рассуждения об играх
10 см., например, Рассел, Б., 1997, с.307, "Человеческое полкаше, его сфера и границы " Ника-Центр, Вист-С, Киев
безотносительно к порядку их выполнения. Важен лишь факт их выполнения или невыполнения. А значит одновременность выполнения, один из синонимов параллельности, выразить с ее помощью невозможно. Нужно иметь средство для описания порядка выполнения игр.
В динамической логике за порядок выполнения отвечает оператор последовательной композиции. Поэтому кажется вполне естественным, на основе анализа его особенностей попытаться построить оператор «парагчетьной композиции». Как следствие, для параллельной композиции а 1113 предполагается полная взаимозависимость игр. Для того чтобы удовлетворять данному требованию каждая из игр или должна иметь какой-либо дефицит информации, восполняемый в процессе параллельной игры, или допускать модификацию данных как, например, в немонотонной логике.
Формально это означает, что каждая из игр, связываемых таким опера юром параллельной композиции, должна содержать открытый параметр, получающий значение извне. В противном случае, выполнение этих игр будет независимым, и, следовательно, не требующим одновременности. Более гого, средств "булевой логики игр" будет вполне достаточно для их описания.
Для передачи значений открытым параметрам, между параллельными играми должен происходить обмен информацией. Игры, между которыми не происходит взаимообмен информацией, не должны называться параллельными. Таким образом, коммуникация между играми является необходимым условием введения параллельных операторов.
В третьем разделе второй главы «Альтернирующая динамическая логика игр» представлена авторская модель расширения динамической логики игр на параллельные операторы. При этом были использованы идеи теоретико-игровой интерпретации мультипликативных связок линейной логики.
Переход к использованию параллельных операторов, сопряжен с трансформацией обычных, одинарных состояний дерева игры, в кратные. Для того чтобы не противоречить семантике Крипке, возможностью расположения сразу в нескольких мирах, с одной стороны, и противоречивостью этих миров, с другой стороны, будем сводить кратные составляющие, получаемые на одном шаге игры, в один мир, но при этом выделять в нем для каждой составляющей отдельные зоны («внутренние миры»).
I ! (
Формализация альтернирующей динамической логики игр (АДЛИ) была выполнена, на основе слегка модернизированной модели Паули, и с использованием изложенных в работе Бласса принципов игровой семантики для мультипликативных операторов линейной логики. В процессе приведения языка выигрышных стратегий Бласса к языку ф'-стратегий Паули, была обнаружена возможность двух принципиально различных, с семантической точки зрения, вариантов АДЛИ, названных АДЛИ 1 и АДЛИ 2. Возможность подобного разделения дала различная трактовка одного из самых выразительных средств логики игр - оператора дуальности. Разница между этими двумя вариантами коснулась также и того, какие типы игр могут быть использованы для подтверждения основной аксиомы - аксиомы копирующей стратегии: [л®тга]ф л (7[©7td)<p." Другими словами, для АДЛИ 1 и АДЛИ 2 типы игр, для которых копирующая стратегия становится ф' - стратегией различаются. Кроме того, благодаря детальному анализу и строгой формализации первоначального расширения логики игр на параллельные операторы,12 была обнаружена его избыточность. Как следствие, были
"®иФ- параллельные операторы тензора и паритета, а данная аксиома выражает то, что в игре с тензором игрок Р имеет выигрышную копирующую стратегию, а в игре с паритетом такую стратегию имеет игрок О
12 Netchitailov, Iou.V., 2001, "An Extension of Game Logic with Parallel Operators" ILLC Scientific Publications, MoL-2001-02, University of Amsterdam, The Netherlands
выделены минимальные А]\ЛИ, которые получили добавочный индекс: «точка два», в то время как «избыточные» варианты стали обозначаться с добавочным индексом: «точка один». Появление минимальной АДЛИ не изменило интерес к предшествующим описаниям, поскольку минимальный вариант применим только для крайне узкого класса игр, в которых копирующая стратегия является ф' - стратегией.
Несмотря на то, что аксиоматика АДЛИ 2.2 не была рассмотрена, можно рассчитывать на подтверждение большинства аксиом АДЛИ 1.1. Однако, при этом, совершенно очевидно, что только для АДЛИ 2 будет верна аксиома (а)ф <-» (аа) |ф, в то время, как только для АДЛИ 1 будет верна аксиома |= <а)ф о [а<|]ф. Данные аксиомы, определяют суть различия в аксиоматике между этими двумя вариантами.
В третьей главе «Модель ограниченной рациональности для динамической логики игр» представляется модель игры с ограниченной рациональностью, для чего, вначале анализируются существующие теоретико-игровые формы представления игр. Рассматриваются возможные причины дефицита информации и способы их описания в теории игр. Затем на основе предложенной модели игр с ограниченной рациональностью, представляется модель динамической логики игр для параллельных игр с двунаправленной коммуникацией, ограниченной рациональностью и произвольным положительным числом участников.
В первом разделе третьей главы «Введение в теоретико-игровую семантику» анализируются экстенсивная и стратегическая (нормальная) формы игры. Поднимается вопрос об учете ресурсов при задании игр.
Получено, что если для отношения вынуждения условие монотонности выполняется всегда, то для стратегии в случае игр ограниченной рациональностью условие монотонности не выполняется. Подобное
расхождение свойств отношения вынуждения и стратегии не существенно для детерминированных конечных игр. Для таких игр предполагается, что игрок знает все стратегии априори. Значит, он сможет идентифицировать нити, дающие финальные состояния отношению вынуждения, но не входящие в стратегию рассматриваемого игрока. В результате, отказавшись от выбора данных нитей в процессе игры, он сможет гарантировать окончание игры в пределах исходной стратегии, т.е. исходного подмножества отношения вынуждения. Однако после введения ограничения на рациональность игроков, а именно, на их знание о стратегиях, отмеченное здесь различие нужно будет учитывать. Для этого будет переопределено отношение вынуждения.
Стратегии для нормальной формы игры не могут быть монотонно расширены. Но если в случае стратегий для игр, записанных в экстенсивной форме, монотонное расширение невозможно только для некоторых игр, например, с ограниченной рациональностью, то для стратегий, записанных в нормальной форме, оно невозможно никогда. По отношению к свойству монотонности стратегия нормальной формы и отношение вынуждения ведут себя по-разному. Помимо этого не понятно как можно задать ограничение рациональности, основываясь на представлении игры в виде нормальной формы. Поэтому за основу, при построении формы игры для случая ограниченной рациональности, следует взять экстенсивную форму.
Во втором разделе третьей главы «Ограниченная рациональность» анализируются возможные причины дефицита информации и способы их описания в теории игр. При создании модели игр с ограниченной рациональностью, на примере шахмат, проводится структурный анализ стратегий, знаний и поведения игроков, выделяются возможные причины, по которым игроки могут не достигать целей в играх с ограниченной
рациональностью С помощью понятия квазивыигрышной стратегии, очерчивает класс игр с ограниченной рациональностью.
Получено, чго относительно друг друта игры с неполной и несовершенной информацией имеют свои плюсы и минусы. К плюсам игр с несовершенной информацией, можно отнести, например, то, что они имеют строгую теоретико-игровую форму. В то же время игры с неполной информацией с теоретико-игровой точки зрения имеют недостаточное описание даже для того, чтобы называться игрой п Значит вне параллельной композиции, которая превращала бы их в полноценную игру, они не могли бы применяться. Зато, с другой стороны, игры с неполной информацией не требуют всеобъемлющего знания об отсутствующей информации В то же время информационные множества игр с несовершенной информацией требуют исчерпывающего описания. В результате класс описываемых игр сужается до тех, для которых мы можем описать все, что нам не известно. Другими словами, в играх с несовершенной информацией нужно уметь полностью формализовать незнание, что в большинстве случаев недостижимо.
Такой элемент игры как стратегия, не обязан быть окончательно определенным до начала игры, а иногда даже и в процессе. Процесс уточнения сгратегии, или того, какой стратегией воспользоваться, может продолжаться вплоть до окончания игры. Данный факт играет важную роль при определении свойств операторов логики игр. В самом деле, для логики действий в роли операторов выступают действия, которые должны быть заданы явно, непосредственно до игры, чтобы игра имела теоретико-игровую форму. В логике игр, в отличие от логики действий в роли операторов выступают игры, а наличие или отсутствие у игрока стратегии сопоставляется с модальностями
" см , например, Вштоге, К, ¡992, "Fun and Games. Л Text on Game Theory" D C. Heath and Company, USA
I
(
1 Поскольку стратегии не обязаны быть окончательно определенными до игры,
)
то и операторы логики игр тоже.
При этом такие игры уже и без использования дополнительных описательных возможностей параллельных операторов являются играми в строгом смысле. Достаточно упомянуть общепринятое представление игр в виде нормальных форм, с характерными для них таблицами результатов для различных последовательностей действий. Для игр, представленных в нормальной форме, игроки могут определить какой из стратегий воспользоваться только для случаев, когда выполняется равновесие Нэша.
Для определяемой модели предположим следующее ограничение рациональности: для конечного числа финальных состояний и нитей игры, вхождение нитей в стратегии не проверяемо Подобное возможно, например, вследствие незнания игроком алгоритма Цермсло, или ограниченности вычислительных ресурсов.
Предполагается, что в условиях ограниченной рациональности, игроки могут воспользоваться квазивыигрышной стратегией, для того, чтобы попытаться форсировать приемлемый для себя результат. Данная стратегия состоит, во-первых, в разбиении сложной задачи, на несколько составляющих, и, во-вторых, с приписыванием каждой задачи промежуточных целей, которые могли бы считаться благоприятными, для успешного решения последующих
р
задач. Подобную тактику используют и шахматисты. В первом приближении, они разбивают одну большую задачу на три последовательных этапа' дебют, миттельшпиль и эндшпиль. На каждом из этапов, в зависимости от локальных целей, они решают отдельную задачу. Совместное решение этих задач, в большинстве случаев, приводит к общему успеху. Так в дебюте целью (задачей) является благоприятное расположение фигур. В миттельшпиле задачей становится достижение материального перевеса, используя благоприятное
расположение фигур. Эндшпиль же предполагается завершать постановкой мата, благодаря созданному материальному перевесу.
Для игр с ограниченной рациональностью выделены две причины, по которы м игроки в предложенной модели могут не достигнуть целей: одна из них связана с тем, что успешные цели могут не совпадать с финальными состояниями стратегий игрока, а другая связана с несогласованностью промежуточных целей при последовательном разбиении задачи. Данные результаты использованы при построении игровой формы для последующего введения параллельных операторов в логику игр. Первый позволил определить игры с ограниченной рациональностью. Благодаря второму результату был специальным образом переопределен оператор последовательной композиции, в результате чего удалось отделить неявное описание целей от явного. Это важно в свете ограниченности вычислительных ресурсов, поскольку неявное описание требует дополнительных затрат ресурсов в ходе решения поставленной проблемы
В третьем разделе третьей главы «Базовые элементы семантики динамической логики игр с ограниченной рациональностью» определяется линейная форма игры соответствующая предложенному классу игр с ограниченной рациональностью. Задается отношение вынуждения для игр с ограниченной рациональностью, которое уже не удовлетворяет условию монотонности. Определяется переход от теоретико-игровой к теоретико-модельной семантике, выделяются явные и неявные способы задания миров. Вводится понятие характеристических формул, достижение которых способны гарантировать игроки в условиях ограниченной рациональности.
Получено, что при добавлении в язык динамической логики игр параллельных операторов мы вынуждены апеллировать к более тонкой, чем сгратегия структуре. При этом в процессе переопределения семантики все же
удается удержаться от перехода к использованию действий. В данной работе показано, что достаточно добавить в описание только нити игры. Полученную в результате этого форму назвали линейной формой игры.
Линейная форма игры может служить адекватным средством представления игр, в которых игрок произвольным образом использует цепочки ходов с успешными финальными состояниями, не зная того, принадлежат ли эти цепочки успешным стратегиям.
Линейная форма игры б это кортеж (Ы, А, Н, О, 5), в котором
• А1= [1,2... к] непустое конечное множество игроков
• А = {а/, а2 ■ ■ ■ ат] непустое конечное множество действий
• Н = {Л/, Й2 ...} множество нитей игры, где И, = {а,/, а,2 ... а,„), для г 6 {/, 2...}, упорядоченные конечные последовательности действий
• й=[Р], Р2 •..} множество диспетчера действий, в котором каждый Л = <Р,/, р,г ■■■ Рт), где р1ге(1, 2... к} номер игрока (ге{2... «}), ставится в соответствие с А, для одного и того же г е {/, 2...}
• 5 = {«о, 5/, 5г • • •} непустое множество, содержащее начальное состояние игры 5о и финальные состояния, в котором каждый х, ставится в соответствие с А,- для одного и того же / е {/, 2...}
Непустой набор нитей игры а, очерчивающий поддерево этой игры, называется стратегией игрока в игре а тогда и только тогда, когда состояния этого поддерева, в которых оппоненты принимают решения, содержат точно такие же, как и в дереве игры а, наборы выходящих непосредственно из них действий.
В четвертом разделе третьей главы «Параллельные игры с ограниченной рациональностью» построена модель динамической логики игр для параллельных игр с двунаправленной коммуникацией, ограниченной рациональностью и произвольным положительным числом участников.
Обозначим выделенного игрока Р (Proponent),., а других игроков О (Opponent!,). В рамках нашей модели мы будем сокращенно обозначать греческой буквой а кортеж (N, А, H, D, S) линейной формы игры. При этом, игру а в которой выделенный игрок играет на позиции leN, будем обозначать а', игру в которой он играет на позиции 2eN, будем обозначать а2, и т.д. В таком случае, легко заметить, что тождество (a')d = а2 означает, что а это игра для дв>х участников. Кроме того, тождества а'=а2=...=ап означают, что ифоки на всех позициях в игре а обладают равными возможностями.
Задается ограниченное отношение вынуждения для произвольного количества игроков. Ограниченное отношение вынуждения рр (а)(и>, F) выражает то, что игрок на позиции Р в игре а, начавшейся в мире w, имеет стратегию, нити которой заканчиваются финальными мирами, формирующими множество F. Обозначение (w, F) е рр(а) используется как равносильное.
Определены следующие свойства ограниченного отношения вынуждения:
(1) немонотонность: из (щ X) е рр(а) и Хс Y не следует что (щ У) е рр(а);
(2) непротиворечивость: Если (щ Y) е р0(а) и (щ Z) е рр(а), то YnZ*0 это возможно, когда в каждом состоянии только один игрок обладает правом выбора следующего действия, либо выбор совершается случайным образом;
(3) неуправляемость: Пусть рр(а) = {(щ ХД (и>, Х2),..., (Щ Хк)}, тогда
V[Z= (J (v\ (iv, X,) 6 рр(а) & V, е X,)] 3[(м, Y) е р0(а)] (Г с Z)
То есть, если взять по одному произвольному миру из каждого множества отношения вынуждения Р, то подмножеству этого множества будет соответствовать одно из отношений вынуждения О. А значит, О сможет форсировать и Y и Z! Данное свойство отражает тот факт, что хотя игрок и может гарантировать достижение одного из миров, принадлежащих одному из множеств его отношения вынуждения, он не в состоянии управлять тем, какой
из миров выбранного множества будет достигнут. Более того, этим процессом может управлять соперник.
Параллельные игры а@р определены следующим образом. Для непустого множества возможных миров X, (щ Х)ерр (а®Р) тогда и только тогда, когда ЗУ, ■£сХ(Уи>'еУ(ил Z)e рР(а) и Уи/'ег (-ш", К)е рР(Р)).
Получено, что сохраняется классическое отношение между модальностями [а]ф = ->{а)-1ф. Однако данная модель динамической логики игр с ограниченной рациональностью исключает возможность использования редукции <а;Р)ф = (сс)(р)ф в обе стороны С точки зрения семантики последнее означает, что мы не можем определить цели игры (а) через неявную формулу (Р)ф, соответствующую несыгранной игре. Это важно, так как, к примеру, в шахматной партии совершенно бесполезно описывать целевые формулы промежуточного этапа а (например, дебюта) через целевые формулы последующего этапа Р (например, миттельшпиля).
Для операторов динамической логики игр можно провести следующие теоретико-игровые аналогии. С помощью операции теста «ф?» игрок Р проверяет, является ли формула ф выполнимой и явной. С помощью операции объединения «аиР» он выбирает одну из двух игр. Операция пересечения «апР» соответствует тому, что другие игроки О выполняют выбор между играми а и р. Оператор параллельной композиции а@р позволяет форсировать некоторые формулы ф, даже если они не являются характеристическими.
Перейти к определенным ранее играм с двумя участниками можно, задав следующее свойство с помощью оператора двойственности- (ту, Х)ерр((а1)'1) тгг (щХ)е рр (а2).
В заключении диссертационной работы подводятся общие итоги исследования, формулируются основные выводы, приведенные в положениях, выносимых на защиту, определяется теоретическое и практическое 'значение
работы, исходя из чего, намечаются перспективы дальнейших исследований.
Указывается как, когда, и где диссертация прошла апробацию
Основные положения диссертации отражены в следующих публикациях
автора (общий объем 3.6 п.л.)
1. Нечитайлов, Ю.В., 2000, "Динамическое обновление информации. Поиск семантики и синтаксиса" Шестая общероссийская конференция «Современная логика: проблемы теории, истории и применения в науке», СПбГУ, Санкт-Петербург, 350-353
2 Netchitailov, lou.V., 2001A, "An Extension of Game Logic with Parallel Operators" ILLC Scientific Publications, MoL-2001-02, University of Amsterdam, The Netherlands
3 Netchitailov, Yu.V., 2001B, "Prospects of an Alternative Semantics for Game Logic with Parallel Operators" Третья международная конференция «Смирновские чтения», Москва, 86-87
4 Нечитайлов, Ю.В., 2002А, "Динамическая Логика Игр с отношением вынуждения и тремя параллельными операторами" Седьмая общероссийская конференция «Современная логика: проблемы теории, истории и применения в науке», СПбГУ, Санкт-Петербург, 481-487
5. Нечитайлов, Ю.В., 2002В, "Коммуникация как необходимый элемент при опредечении паратлечьных игр" Международная научная конференция «Информация коммуникация общество» ИКО-2002, ЛЭТИ, Санкт-Петербург, 213-215
6. Нечитайлов, Ю.В., 2003А, "Модель ограниченной рациональности для Логики игр" Четвертая международная конференция «Смирновские чтения», Москва, 164-166
7. Нечитайлов, Ю.В., 2003В, "Учет ограниченности ресурсов при построении динамической логики игр" Международная научная конференция «Информация коммуникация общество» ИКО-2003, ЛЭТИ, Санкт-Петербург, 305-307
8. Нечитайлов, Ю.В., 2003С, "Парачлельная композиция в динамической логике игр с ограниченной рациональностью" Логические исследования, Вып. 10, Москва, 142-149
/Ч
рос. нлциьал«»»!!..
БИБЛИОТЕКА СОсп»%*г О» Ж иг
ЛР № 040815 от 22.05 97.
шсано к печати 05 12 2003 г Формат бумаги 60X84 1/16 Бумага офсетная Печать ризографическая Объем 1,5 п л Тираж 100 экз Заказ 3090 Отпечатано в отделе оперативной полиграфии НИИХ СПбГУ с оригинал-макета заказчика 198504, Санкт-Петербург, Старый Петергоф, Университетский пр., 26
Р- - . 7
РНБ Русский фонд
2004-4 17911
Оглавление научной работы автор диссертации — кандидата философских наук Нечитайлов, Юрий Вячеславович
Введение.
Глава 1. Границы развития интенсиональной доктрины.
1.1. Проблемы и парадоксы экстенсиональной логики.
1.1.1. Структур а формализованного языка. а) Формальная система. б) Семантические правила интерпретации.
1.1.2. Особенности экстенсионального и интенсионального подходов в логической семантике. а) Экстенсиональное направление. б) Парадоксы интенсионального контекста. в) Революция в интенсиональном направлении.
1.2. От описания корректности работы программ к описанию работы недетерминированных систем.
1.2.1. Логика Хоара как альтернатива тестированию.
1.2.2. Средний терм в динамической логике и логике игр. а) Динамическая логика. б) От процессов к играм. в) Динамическая логика игр.
1.3. Язык как средний терм при переносе информации.
1.3.1.Компиляторы и их корректность.
1.3.2.Проблема передачи знания.
Глава 2. Подходы к описанию параллельных процессов и игр.
2.1. Опыт описания параллельных процессов.
2.1.1. Параллелизм в математике, логике и теоретической информатике. а) Алгебра параллельных процессов. б) Конкурентная динамическая логика. в) Мультипликативная линейная логика. г) Сети Петри.
2.1.2. Параллелизм в теории формальных языков. а) Индийская и русская параллельные грамматики. б) Системы Линденмайера. в) Колонии. г) Взаимодействующие распределенные системы грамматик. д) Системы эко грамматик. е) Параллельные коммуникативные системы грамматик. ж) Параллельные коммуникативные системы Линденмайера. з) Траектории для операции тасования.
2.2. Смысл параллелизма для логики.
2.2.1. Естественнонаучные корни метафоры параллелизма.
2.2.2.Роль коммуникации для параллельных игр.
2.3. Альтернирующая динамическая логика игр.
2.3.1. Уточнение семантики.
2.3.2. Модель АДЛИ1.1.
2.3.3. Аксиоматика АДЛИ 1.1.
Глава 3. Модель ограниченной рациональности для динамической логики игр.
3.1. Введение в теоретико-игровую семантику.
3.1.1. Экстенсивная форма. Стратегия и отношение вынуждения.
3.1.2. Стратегическая форма.
3.1.3. Учет ресурсов при задании игр.
3.2. Ограниченная рациональность.
3.2.1. Виды дефицита информации.,.
3.2.2.Подход к описанию игр с ограниченной рациональностью. а) Информированность игроков о состояниях, действиях и стратегиях. б) Успешные нити и выигрышные стратегии. в) Квазивыигрышная стратегия.
3.3. Базовые элементы семантики динамической логики игр с ограниченной рациональностью.
3.3.1.Игра и линейная форма ее представления.
3.3.2. Отношение вынуждения для игр с ограниченной рациональностью.
3.3.3.0т теоретико-игровых состояний к теоретико-модельным мирам.
3.3.4. Явные и неявные способы описания миров.
3.4. Параллельные игры с ограниченной рациональностью.
3.4.1.Игровая форма и модель игры.
3.4.2. Синтаксис и семантика.
Введение диссертации2003 год, автореферат по философии, Нечитайлов, Юрий Вячеславович
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы
Логика Хоара была разработана для того, чтобы можно было, избегая тестирования, проверять работоспособность программ и точно описывать выдаваемый результат. Логика Хоара имела ряд недостатков, ограничивающих область ее применения, которые были устранены в динамической логике. В процессе развития вычислительных систем пользователь постепенно стал оказывать все большее и большее влияние на ход выполнения программ. В результате чего потребовался переход к теоретико-игровой семантике. Развитие динамической логики игр, обладающей такой семантикой, может приблизить нас к созданию инструмента для верификации человеко-машинных систем. Подобным многопользовательским системам характерна параллельная обработка информации в условиях ограниченности ресурсов.
Между тем современная логика не имеет достаточных средств, описывающих параллельные системы с ограниченными ресурсами. Большинство логических моделей построено с расчетом на неограниченную рациональность. Эта неограниченность не имеет ничего общего с ответами Оракула, способного, неведомым нам способом, решить любую проблему. Концепция неограниченной рациональности имеет несколько аспектов. Допустим, что человеко-машинная система решает некоторую задачу. Тогда, во-первых, в случае неограниченной рациональности считается, что все участники системы владеют исчерпывающей информацией обо всем, что в ней происходит и находится, или, по крайней мере, существует алгоритм, позволяющий им получить такую информацию. Во-вторых, если эта задача
1 Работа выполнена при поддержке РГНФ, грант № 03-03-00455а разрешима на машине Тьюринга, то предполагается, что ее решение представлено в описываемой системе, вне зависимости от сложности этой задачи, т.е. затрата материальных и временных ресурсов не учитывается. Саймон {Simon, Н.А., 1978) в своей Нобелевской лекции подчеркивал эмпирическую ограниченность таких описаний для теории принятия решений. Совершенно очевидна их ограниченность и для прикладных задач информатики. Например, на данный момент не существует «чудо компьютера», способного просчитать все ходы шахмат. Но поскольку шахматы являются конечной игрой с четко определенными ходами, то в случае использования логики, предполагающей неограниченную рациональность, придется считать, что один из игроков имеет выигрышную стратегию. Однако такой подход видится не очень естественным.
За последние сорок лет представлено множество формализации параллельных процессов в теоретической информатике и теории формальных языков. Существует и математическая модель: алгебра параллельных процессов. К сожалению, в логике эта тема почти не отражена. Этот факт показывает не консервативность логики, а технические трудности представления параллелизма логическими средствами, без нарушения существующих концепций. Помимо того, что новые операторы/связки нужно суметь связать со старыми, с помощью новых операторов нужно попытаться выразить нечто новое, не сводимое к уже известным операторам. Иначе особого смысла нововведения иметь не будут.
Параллелизм в логике представлен в теоретико-игровой интерпретации линейной логики, идеи которой были использованы мной при создании первого расширения динамической логики игр на параллельные операторы. Это расширение позволило выявить некоторые свойства и закономерности, присущие параллельным играм. Оказалось, что, в случае этого расширения, параллельные операторы не сводимы к непараллельным, только для игр с несовершенной информацией, или подобным им. Была обнаружена и успешно решена проблема кратных миров. К сожалению, параллельные операторы в этом расширении связаны с копирующей стратегией, позволяющей добиваться победы только в двойственных играх. Сама копирующая стратегия кажется несколько искусственной, а область ее применения довольно узкой. Кроме того, такой подход позволяет задавать новые операторы неограниченно, связывая их с новыми стратегиями розыгрыша параллельных игр. При построении новых стратегии могут быть использованы различные основания: структурные особенности игр, соотношение свойств классов игр, и т.п. Для логических систем такие стратегии было бы естественнее связывать с набором предикатов, а не операторами, потому, что логические операторы не должны решать какие-то локальные задачи. Они должны иметь описание, не зависящее от конкретного типа задач. Не смотря на то, что каждая из этих стратегий позволяет построить решение для целого класса игр, обобщения, обосновывающего введение единого, не зависящего от конкретного типа задач, параллельного оператора (или нескольких операторов), с их помощью получить нельзя. Для нахождения общего основания введения параллельных операторов, полезно будет выяснить: почему одну пару игр мы считаем параллельной, а другую нет.
Еще одной системой, описывающей параллельные процессы, является конкурентная динамическая логика. Однако, во-первых, использование теоретико-игровой семантики для этой логики совсем не очевидно, а, во-вторых, способ определения оператора совмещения мне представляется довольно спорным. Он идет вразрез с теоретико-модельной семантикой Крипке, согласно которой, вычислительный процесс не может оказаться одновременно в нескольких мирах. Я вовсе не считаю, что от семантики
Крипке нельзя отклоняться, но, по-моему, это следует делать только в случае крайней необходимости.
Повсеместное распространение сетевых решений, в частности благодаря развитию телефонных коммуникаций и Интернета, поднимают вопрос о гарантиях стабильности работы создаваемых систем. Проверка работоспособности таких систем путем эксплуатации, или тестирования, в течение определенного промежутка времени не способна показать отсутствие ошибок, а лишь позволяет выявлять некоторые из них. Учитывая повсеместное внедрение сетевых решений, следует ожидать, что цена не выявленных ошибок может оказаться огромной.
Исходя из сказанного, анализ аспектов параллелизма, которые могут быть выражены в логике, расширение динамической логики игр на параллельные операторы, и исследование моделей игр с ограниченной рациональностью представляются актуальными.
Степень разработанности темы
В 50е-60е годы XX века появились и теория игр, за вклад в которую Харсани (Harsanyi), Нэш (Nash) и Селтен (Selteri) в 1993 году получили Нобелевскую премию, и, связанные с ней, математические логические игры (Lorenzen, Ehrenfeucht/Frai'sse, 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;
• «Международная Научная Конференция: Информация Коммуникация Общество ИК02002», ЛЭТИ, Санкт-Петербург; ноябрь 2002;
• «Четвертые Смирновские чтения», Сектор логики Института философии РАН май 2003;
• «Международная Научная Конференция: Информация Коммуникация Общество ИК02003», ЛЭТИ, Санкт-Петербург; ноябрь 2003;
Отдельные положения диссертации использованы автором при проведении серии семинаров «Логика, Игры, Коммуникация» в Санкт-Петербургском Государственном Университете. Диссертационные исследования поддержаны РГНФ: грант на 2003 год. Некоторые материалы данного исследования опубликованы в сборнике «Логические исследования» за 2003 год. Диссертация обсуждена на заседании кафедры логики философского факультета СПбГУ.
Структура и объем диссертации
Диссертация изложена на 200 страницах. Общая структура диссертационного исследования определяется её основной целью и задачами. Текст диссертации содержит введение, три главы, заключение и список литературы из 75 наименований на русском и английском языках.
Заключение научной работыдиссертация на тему "Проблема формализации концепций параллелизма и ограниченной рациональности средствами динамической логики игр"
Основные выводы сформулированы в следующих положениях, выносимых на защиту.
1) Проблема «средней формулы», описывающей общее состояние системы при декомпозиции сложных процессов является неустранимой, т.е. для любой формальной системы существует модель, для которой, несмотря на то, что средняя формула существует, она является невыразимой на языке этой формальной системы
2) Между процессом приобретения языковых навыков ребенком, и процессом приобретения языковых навыков антропологом при изучении языка аборигенов, имеется существенная разница. Главное отличие в том, что первый процесс можно считать скорее биолого-лингвистическим, в то время как второй — скорее формально-лингвистическим.
3) Объектная и операционная семантики взаимообусловлены, и, в структуре языка, не могут существовать друг без друга. Без операционной семантики не будет инструмента, позволяющего сделать первый шаг для наполнения объектной семантики. Отказ от объектной семантики приведет к тому, что, или нечего будет наполнять, или операционная семантика сама станет объектной.
4) С точки зрения описания процесса передачи знания, динамическая логика игр с параллельными операторами и ограниченной рациональностью полезна для формализации и исследования проблем формально-лингвистической коммуникации.
5) В формальных системах понятие параллелизма, в одних случаях, используется для описания полностью независимых процессов, в других случаях, напротив, для описания взаимозависимых процессов с непосредственной или опосредованной связью. Параллельные операторы в логике имеет смысл вводить только для взаимозависимых игр. Включение описания для полностью независимых параллельных игр потребует принципиального изменения семантики Крипке.
6) Для динамической логики игр с ограниченной рациональностью отношение вынуждения должно быть немонотонным, в отличие от динамической логики игр с неограниченной рациональностью.
7) Понятие квазивыигрышной стратегии очерчивает класс игр с ограниченной рациональностью, для которых построена модель динамической логики игр для параллельных игр с двунаправленной коммуникацией, ограниченной рациональностью и произвольным положительным числом участников Теоретическое и практическое значение диссертации
Результаты, полученные в данной диссертации, могут быть использованы для описания параллельных процессов с двунаправленной коммуникацией ограниченной рациональностью и неограниченным положительным числом участников. Это может помочь приблизиться к формализации процесса передачи знания, в процессе формально-лингвистической коммуникации. Кроме того, результаты могут быть использованы для дальнейших исследований игр с ограниченной рациональностью, а также для поиска описания логическими средствами других классов параллельных игр. Материал диссертации может быть использован при создании учебных курсов.
Апробация работы
Некоторые материалы данного исследования изложены в публикации, изданной в научной серии Университета Амстердама, а также были представлены на одном из выступлений в Институте Логики, Языка и Вычислений (Университет Амстердама).
Материалы данного исследования представлялись в виде публикаций тезисов и докладов на следующих конференциях:
• «Третьи Смирновские чтения», Сектор логики Института философии РАН, май 2001;
• «Седьмая Общероссийская Конференция Современная логика: проблемы теории, истории и применения в науке», СПбГУ, Санкт-Петербург, июнь 2002;
• «Международная Научная Конференция: Информация Коммуникация Общество ИК02002», ЛЭТИ, Санкт-Петербург; ноябрь 2002;
• «Четвертые Смирновские чтения», Сектор логики Института философии РАН май 2003;
• «Международная Научная Конференция: Информация Коммуникация Общество ИК02003», ЛЭТИ, Санкт-Петербург; ноябрь 2003;
Отдельные положения диссертации использованы автором при проведении серии семинаров «Логика, Игры, Коммуникация» в Санкт-Петербургском Государственном Университете. Диссертационные исследования поддержаны РГНФ: грант на 2003 год. Некоторые материалы данного исследования опубликованы в сборнике «Логические исследования» за 2003 год. Диссертация обсуждена на заседании кафедры логики философского факультета СПбГУ. У
Заключение
В результате исследования были раскрыты мотивы использования интенсиональных логик, рассмотрены их выразительные возможности. На основе анализа проблемы средней формулы, исследована полнота выразительных средств интенсиональных логик. Обоснованы причины введения параллельных операторов и ограниченной рациональности в динамическую логику игр, и очерчен круг проблем, описываемых с их помощью. Проведены междисциплинарное исследование и систематизация опыта описания параллельных процессов, проанализированы естественнонаучные корни метафоры параллелизма, и выявлена специфика использования атрибута параллельности в логике. Представлена модель динамической логики игр с параллельными операторами: альтернирующая динамическая логика игр. Представлена модель игры с ограниченной рациональностью. Рассмотрены возможные причины дефицита информации и способы их описания в теории игр. На основе предложенной модели игр с ограниченной рациональностью, представлена модель динамической логики игр для параллельных игр с двунаправленной коммуникацией, ограниченной рациональностью и произвольным положительным числом участников.
Список научной литературыНечитайлов, Юрий Вячеславович, диссертация по теме "Логика"
1. Берн, Э., 1992, "Игры, в которые играют люди. Психология человеческих взаимоотношений; Люди, которые играют в игры. Психология человеческой судьбы" СПб., Лениздат
2. Бородай, ЮМ., 1996, "Эротика смерть - табу: трагедия человеческого сознания" Москва, «Гнозис»
3. Лавров, И.А., Максимова, Л.Л., 1995, "Задачи по теории множеств, математической логике и теории алгоритмов" Москва, «Физико-математическая литература»
4. Лоръер, Ж.-Л., (Laurikre Jeane-Louis), 1991, "Системы искусственного интеллекта" Москва, «Мир»
5. Марков, А.А., Нагорный, Н.М., 1996 "Теория алгорифмов" Москва, «Фазис»
6. Матурана, У., 1996, "Биология познания" Язык и интеллект, Сборник, Сост. и вступ. ст. В.В. Петрова, Москва, Издательская группа «Прогресс»
7. Непейвода, Н.Н., 1997, "Прикладная логика" Издательство Удмуртского университета, Ижевск
8. Нечитайлов, Ю.В., 2000, "Динамическое обновление информации. Поиск семантики и синтаксиса" Шестая общероссийская конференция «Современная логика: проблемы теории, истории и применения в науке», СПбГУ, Санкт-Петербург, 350-353
9. Нечитайлов, Ю.В., 2002А, "Динамическая Логика Игр с отношением вынуждения и тремя параллельными операторами" Седьмая общероссийская конференция «Современная логика: проблемы теории, истории и применения в науке», СПбГУ, Санкт-Петербург, 481-487
10. Нечитайлов, Ю.В., 2002В, "Коммуникация как необходимый элемент при определении параллельных игр" Международная научная конференция «Информация коммуникация общество» ИКО-2002, ЛЭТИ, Санкт-Петербург, 213-215
11. Нечитайлов, Ю.В., 2003А, "Модель ограниченной рациональности для Логики игр" Четвертая международная конференция «Смирновские чтения», Москва, 164-166f
12. Нечиташов, Ю.В., 2003В, " Учет ограниченности ресурсов при построении динамической логики игр" Международная научная конференция «Информация коммуникация общество» ИКО-2003, ЛЭТИ, Санкт-Петербург, 305-307
13. Нечиташов, Ю.В., 2003С, "Параллельная композиция в динамической логике игр с ограниченной рациональностью" Логические исследования, Вып.10, Москва, 142-149
14. Пригожим, И.С., 1991, "Философия нестабильности" Вопросы философии, N6,46-57
15. Рассел, Б., 1997, "Человеческое познание, его сфера и границы" Ника-Центр, Вист-С, Киев
16. Серл,Д., 1998, "Сознание, мозг и программы" Аналитическая философия: становление и развитие. Москва
17. Смирнова, Е.Д., Таванец, П.В., 1967, "Семантика в логике" Логическая семантика и модальная логика, Издательство «Наука», Москва, 3-53
18. Abramsky, S., Jagadeesan, R., 1994, "Games and Full Completeness for Multiplicative Linear Logic" The Journal of Symbolic Logic, Volume 59, Number 2, 543-574
19. Anderson, A.C., 1998, "Alonzo Church's Contributions to Philosophy and Intentional Logic" The Bulletin of Symbolic Logic, Volume 4, Number 2,129-171
20. Anderson, A.C., 1984, "General Intentional Logic" Handbook of Philosophical Logic, Volume II, Eds. D. Gabbay and F. Guenthner, D. Reidel Publishing Company, Kluwer Academic Publishers, 355-385
21. Baeten, J.C.M., Verhoef, C., "Concrete process algebra" Handbook of Logic in Computer
22. Science, Volume 4, 149-268
23. Binmore, K., 1992, "Fun and Games. A Text on Game Theory" D.C. Heath and Company, USAi*
24. Blackburn, P., Bos, J., 2001, "An Introduction to Computational Semantics" Foundational Course, ESSLLIХП1, Helsinki
25. Blass, A., 1992, "A Game Semantics for Linear Logic" Annals of Pure and Applied Logic, Volume 56, 183-220
26. Chomsky, N., 1957, "Syntactic Structures" Mouton, The Hague
27. Church, A„ 1956, "Introduction to Mathematical Logic" Volume 1, Princeton University Press, Princeton, New Jersey
28. Ciobanu, G., Rotaru, M„ 2001, "JC-Nets" MCU 2001, LNCS 2055, Ed. M. Margenstern and Y. Rogozhin, 190-201
29. Csuhaj-Varju, E., Dassow, J., Kelemen, J., Paun, Gh., 1994, "Grammar Systems a Grammatical Approach to Distribution and Cooperation " Gordon and Breach, LondonM
30. Dassow, J., Kelemen, J., Paun, Gh., 1993, "On parallelism in colonies" Cybernetics and Systems, Volume 24, 37-49
31. Gifford, D.K., Winfree, E., eds., 2000, "DNA Based Computers V" American Mathematical Society, Providence, RI39.
