О некоторых вариантах понятия реализуемости тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

Введение.

1. Предварительные сведения 7 1.1. Сведения из логики.!.

1.1.1. Основные определения

1.1.2. Логика слабого закона исключённого третьего

1.1.3. Свойства позитивных формул.

4 1.2. Алгоритмы и количество информации.

1.2.1. Алгоритмы.

1.2.2. Количество информации.

2. Алгоритмические задачи

2.1. Определение и основные свойства.

2.1.1. Операции над множествами.

2.1.2. Интерпретация классической логики.

2.1.3. Интуиционистская логика и реализуемость

2.1.4. Сложность алгоритмических задач.

2.1.5. Простейшие логические свойства.

2.2. Оценки на сложность задач

2.2.1. Нижняя оценка для критических импликаций

2.2.2. Классификация формул по сложности порождаемых алгоритмических задач.

2.2.3. Верхние оценки для критических импликаций

2.2.4. О мощности множеств, на которых достигается нижняя оценка сложности

3. Финитные задачи

3.1. Основные свойства финитных задач

3.1.1. Определение.

3.1.2. Утверждения о корректности.

3.1.3. Финитные задачи и логика.

3.2. Достаточное множество решений.

3.2.1. Определение и простейшие свойства.

3.2.2. Нижняя оценка для критических импликаций

3.2.3. Классификация формул по мощности достаточного множества решений.

3.2.4. Об оптимальности оценки для критических импликаций.

3.3. Колмогоровская сложность финитных задач.

3.3.1. Определение и простейшие свойства.

3.3.2. Классификация формул по сложности порождаемых финитных задач.

Классическая логика изучает истинность и ложность высказываний, полученных из некоторых исходных элементарных высказываний при помощи логических операций V, Л, —>, -ч, называемых также логическими связками.

А.Н.Колмогоров в своей статье [16], написанной в 1932 году, предложил рассматривать аналогичные операции не над высказываниями, а над задачами. Логические связки в этом случае используются для построения составной задачи из нескольких исходных элементарных задач. Например, для задач А и В их конъюнкция А А В есть задача „решить обе задачи А и Б", а импликация А —> В — „указать общий метод, позволяющий из решения задачи А получить решение задачи В".

В некоторых случаях решение составной задачи можно указать, даже не зная использованных элементарных задач, а зная лишь структуру составной задачи, то есть задающую её формулу. Такова, например, задача вида А —> А. Колмогоров в статье [16] указывал, что множество формул, для которых можно указать заранее некоторое решение составной задачи, естественно назвать конструктивной логикой. Так определённое „исчисление задач" он рассматривал как новый подход к построению интуиционистской логики, отличный от философских рассмотрений Брауэра.

Колмогоров ограничился лишь несколькими примерами элементарных задач и неформальным описанием операций, но не сформулировал математически строгой семантики, подобной той, которую булевы функции предоставляют для классической логики. Впоследствии было предложено несколько вариантов семантики, следующей этим идеям. Первым было понятие реализуемости, / предложенное С. К. Клини (1945). На несколько других принципах основывались интерпретации, введённые Ю. Т. Медведевым — исчисление массовых проблем (1955) и финитная общезначимость (1961).

Логика реализуемости (точнее, разные варианты такой логики) и логика финитных задач активно изучались разными исследователями. Довольно быстро было установлено, что эти логики расширяют интуиционистскую логику высказываний, но не совпадают с ней, и встал вопрос об их синтаксическом описании. Для логики финитных задач была доказана невозможность конечной аксиоматизации, для логики реализуемости этот вопрос остаётся открытым. Также не доказана и не опровергнута ни разрешимость, ни перечислимость этих логик.

Настоящая диссертация посвящена подходу, основанному на некоторой модификации исходной идеи Колмогорова. Этот подход был предложен А. Шенем (см. [19]) и опирается на понятие количества информации, рассмотренное Колмогоровым в 1965 году. Основная идея подхода состоит в следующем.

У любой задачи есть важный параметр — минимальное количество информации, достаточное для её решения. Пропозициональная формула, понимаемая как операция над задачами, задаёт некоторую связь между значениями этого параметра для задач-аргументов и задачи-результата. Рассмотрим те формулы, для которых у любой задачи, полученной подстановкой каких-то задач в эту формулу, количество информации, достаточное для её решения, очень мало по сравнению с количеством информации, необходимым для решения подставленных задач (например, ограничено единой константой для всех подставляемых задач). Естественно сказать, что такие формулы задают задачи, которые можно „почти решить" заранее.

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

Таким образом, возникает следующий вопрос: каков класс пропозициональных формул, для которых некоторое решение задачи, полученной подстановкой в эту формулу, всегда можно указать, используя „небольшое" количество информации?

Для ответа на этот вопрос нужно строго определить, что понимается под задачей, какие операции над задачами сопоставлены логическим связкам, как измеряется количество информации, наконец, каков точный смысл слова „небольшое".

В диссертации рассмотрены два подхода к определению задач и операций над ними: реализуемость (соответствующие задачи названы здесь алгоритмическими) и финитные задачи по Медведеву. Для измерения количества информации в случае алгоритмических задач используется колмогоровская сложность, а в случае финитных задач — мощность „достаточного множества решений" и колмогоровская сложность (это соответствует двум подходам к определению количества информации из статьи [5], комбинаторному и алгоритмическому). Доказано, что для разнообразных ограничений на количество информации в решении (в случае кол-могоровской сложности — для всех естественных ограничений) возникает один и тот же класс формул — логика слабого закона исключённого третьего 3. Доказательства используют характери-зацию логики 5 при помощи формул специального вида — критических импликаций — вытекающую из работ Янкова и Медведева.

Диссертация разбита на три главы.

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

Во второй главе изучается интерпретация логических связок как операций над алгоритмическими задачами. В первой части главы даны основные определения, описана связь рассматриваемого понятия с понятием реализуемости, и доказаны простые оценки на сложность задач. Во второй части главы доказаны основные результаты, и в частности, нижняя оценка сложности для критических импликаций. Также приведены некоторые оценки, дополняющие основные результаты.

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

Автор глубоко благодарен своему научному руководителю Н. К. Верещагину за постановку задачи и последующее постоянное участие и помощь в работе. Автор благодарит А. Шеня, В. Е. Плис-ко и особенно Д. П. Скворцова за полезные обсуждения. Автор признателен В. А. Успенскому, С. И. Адяну и всем сотрудникам кафедры математической логики и теории алгоритмов механико-математического факультета МГУ за благожелательное внимание к работе.

1. Ф. Л. Варпаховский. К вопросу об аксиоматизации реализуемых пропозициональных формул. Доклады АН СССР, 1990, т. 314, вып. 1, с. 32-36.

2. Н.К.Верещагин, А.Шень. Языки и исчисления. М.: МЦНМО, 2000.

3. А.К.Звонкин, Л.А.Левин. Сложность конечных объектов и обоснование теории информации и случайности с помощью теории алгоритмов. Успехи математических наук, 1970, т. 25, № 6, с. 85-127.

4. С. К.Клини. Введение в метаматематику. М.: ИЛ, 1957.

5. А. Н. Колмогоров. Три подхода к определению понятия „количество информации". Проблемы передачи информации, 1965, т. 1, № 1, с. 3-11.

6. Л. Л. Максимова, Д. П. Скворцов, В. Б. Шехтман. Невозможность конечной аксиоматизации логики конечных задач Медведева. Доклады АН СССР, 1979, т. 245, вып. 5, с. 1051-1054.

7. Ю.Т.Медведев. Финитные задачи. Доклады АН СССР, 1962, т. 142, вып. 5, с. 1015-1018.

8. Ю.Т.Медведев. Интерпретация логических формул посредством финитных задач и связь её с теорией реализуемости. Доклады АН СССР, 1963, т. 148, вып. 4, с. 771-774.

9. Ю.Т.Медведев. Об интерпретации логических формул посредством финитных задач. Доклады АН СССР, 1966, т. 169, вып. 1, с. 20-24.

10. В.Е. Плиско. О реализуемых предикатных формулах. Доклады АН СССР, 1973, т. 212, вып. 3, с. 553-556.

11. В.Е.Плиско. Абсолютная реализуемость предикатных формул. Известил АН СССР, сер. матем., 1983, т. 47, вып. 2, с. 315-334.

12. В. Е. Плиско. О языках с конструктивными логическими связками Доклады АН СССР, 1987, т. 296, вып. 1, с. 35-38.

13. В. А.Янков. Об исчислении слабого закона исключённого третьего. Известия АН СССР, сер. матем., 1968, т. 32, вып. 5, с. 1044-1051.

14. В.А.Янков. О связи между выводимостью в интуиционистском исчислении высказываний и конечными импликативны-ми структурами. Доклады АН СССР, 1963, т. 151, вып. 6, с. 1293-1294.

15. S. С. Kleene. On the interpretation of intuitionistic number theory. Journal of Symbolic Logic, 1945, v. 10, pp. 109-124.

16. A. Kolmogoroff. Zur Deutung der intuitionistishen Logik. Mathematische Zeitschrift, 1932, Bd. 35, H. 1, S. 58-65.

17. M.Li, P. Vitanyi. An Introduction to Kolmogorov Complexity and Its Applications. New York, Springer-Verlag, 1997.

18. G. F. Rose. Propositional calculus and realizability. Transactions of the American Mathematical Society, 1953, v. 75, № 1, pp. 1-19.

19. A. Shen, N. Vereshchagin. Logical operations and Kolmogorov complexity. Theoretical Computer Science, 2002, v. 271, pp. 125-129.Работы автора по теме диссертации

20. А.В.Чернов. Финитные задачи и логика слабого закона исключённого третьего. Рукопись депонирована в ВИНИТИ 03.07.2003, № 1263-В2003, 15 с.