Проблема формализации концепций параллелизма и ограниченной рациональности средствами динамической логики игр тема диссертации и автореферата по ВАК РФ 09.00.07, кандидат философских наук Нечитайлов, Юрий Вячеславович

• Нечитайлов, Юрий Вячеславович
• кандидат философских наук
• 2003

Оглавление диссертации кандидат философских наук Нечитайлов, Юрий Вячеславович

Введение.

Глава 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. Синтаксис и семантика.

Введение диссертации (часть автореферата) на тему «Проблема формализации концепций параллелизма и ограниченной рациональности средствами динамической логики игр»

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы

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

Между тем современная логика не имеет достаточных средств, описывающих параллельные системы с ограниченными ресурсами. Большинство логических моделей построено с расчетом на неограниченную рациональность. Эта неограниченность не имеет ничего общего с ответами Оракула, способного, неведомым нам способом, решить любую проблему. Концепция неограниченной рациональности имеет несколько аспектов. Допустим, что человеко-машинная система решает некоторую задачу. Тогда, во-первых, в случае неограниченной рациональности считается, что все участники системы владеют исчерпывающей информацией обо всем, что в ней происходит и находится, или, по крайней мере, существует алгоритм, позволяющий им получить такую информацию. Во-вторых, если эта задача

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 год. Диссертация обсуждена на заседании кафедры логики философского факультета СПбГУ. У

Заключение

В результате исследования были раскрыты мотивы использования интенсиональных логик, рассмотрены их выразительные возможности. На основе анализа проблемы средней формулы, исследована полнота выразительных средств интенсиональных логик. Обоснованы причины введения параллельных операторов и ограниченной рациональности в динамическую логику игр, и очерчен круг проблем, описываемых с их помощью. Проведены междисциплинарное исследование и систематизация опыта описания параллельных процессов, проанализированы естественнонаучные корни метафоры параллелизма, и выявлена специфика использования атрибута параллельности в логике. Представлена модель динамической логики игр с параллельными операторами: альтернирующая динамическая логика игр. Представлена модель игры с ограниченной рациональностью. Рассмотрены возможные причины дефицита информации и способы их описания в теории игр. На основе предложенной модели игр с ограниченной рациональностью, представлена модель динамической логики игр для параллельных игр с двунаправленной коммуникацией, ограниченной рациональностью и произвольным положительным числом участников.

Список литературы диссертационного исследования кандидат философских наук Нечитайлов, Юрий Вячеславович, 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.