Наборы конечных объектов с заданными информационными соотношениями между ними

Вьюгин, Михаил Владимирович

Наборы конечных объектов с заданными информационными соотношениями между ними тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

Вьюгин, Михаил Владимирович АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Москва МЕСТО ЗАЩИТЫ

2004 ГОД ЗАЩИТЫ

01.01.06 КОД ВАК РФ

Диссертация по математике на тему «Наборы конечных объектов с заданными информационными соотношениями между ними»

Автореферат диссертации на тему "Наборы конечных объектов с заданными информационными соотношениями между ними"

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М.В.ЛОМОНОСОВА МЕХАНИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

На правах рукописи УДК 519.722+510.5

Вьюгин Михаил Владимирович

НАБОРЫ КОНЕЧНЫХ ОБЪЕКТОВ С ЗАДАННЫМИ ИНФОРМАЦИОННЫМИ СООТНОШЕНИЯМИ МЕЖДУ НИМИ

Специальность 01.01.06 - математическая логика, алгебра и теория чисел

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

МОСКВА 2004

Работа выполнена на кафедре математической логики и теории алгоритмов механико-математического факультета Московского государственного университета имени М. В. Ломоносова.

Научный руководитель — доктор физико-математических наук,

профессор Н. К. Верещагин.

Официальные оппоненты — доктор физико-математических наук,

профессор А. Л. Семенов; кандидат физико-математических наук, А. Е. Ромащенко.

Ведущая организация — Институт вычислительных технологий

СО РАН.

Защита диссертации состоится "/7 " М&1, 2004- г. в 16 ч. 15 мин.

на заседании диссертационного совета Д.501.001.84 при Московском государственном университете им. М. В. Ломоносова по адресу: 119899, ГСП, Москва, Воробьевы горы, МГУ, механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке механико-математического факультета МГУ (Главное здание, 14 этаж).

Автореферат разослан г.

Ученый секретарь диссертационного совета Д.501.001.84 при МГУ доктор физико-математических наук профессор

В. Н. Чубариков

Общая характеристика работы

Актуальность темы. А. Н. Колмогоров в работе [Koll]1 выделил три похода к определению понятия "количество информации": комбинаторный, вероятностный и алгоритмический. Вероятностный подход основан на понятии энтропии Шеннона тогда как алгоритмический - на введенном Колмогоровым понятии алгоритмической сложности. Классическая теория информации Шеннона рассматривает случайные величины, в то время как алгоритмическая теория информации Колмогорова имеет дело с индивидуальными объектами. Тем не менее, многие утверждения могут, после соответствующей переформулировки, быть перенесены из первой теории во вторую (примеры можно найти в работах [Mul]2, [HRSV]3; также см. Теорему 3, приведенную далее, доказанную Ан. А. Мучником и опубликованную в [Ми2]4). Получающиеся аналоги, как и все результаты теории алгоритмической сложности, имеют асимптотический характер и выполнены лишь с определенной точностью. Наилучшая возможная точность - с точностью до аддитивной константы. Однако большинство известных результатов вышеописанного типа выполнены с точностью до аддитивного члена порядка логарифма алгоритмической сложности рассматриваемых объектов.

В данной работе нас интересует вопрос о том, выполнены ли эти аналоги с большей точностью. Это становится существенным, если мы интересуемся сложными объектами, которые мало (по сравнению со своей сложностью) отличаются друг от друга. Если нам все же важно количество информации, необходимое для преобразования одного из этих объектов в другой, необходимо более тонкое рассмотрение, а именно рассмотрение с точностью до аддитивного члена, зависящего от условной алгоритмической сложности.

Если упомянутые алгоритмические аналоги теорем классической теории информации перестают быть верными с большей точностью, мож-

l[Koll] Колмогоров А.Я. Три подхода к определению понятия " количество информации ". // Проблемы передачи информации, 1965. Т. 1, номер X, С. 3-11.

'[Mul) Mvchnik An. A. On Common Information. // Theoretical Computer Science. 1998. V. 207, P. 319-328

S[HRSV] Hammer D., Romashchenko A., Shen A., Vertshchagin N. Inequalities for Shannon Entropy and Kotmogorov Complexity. // Journal of Computer and System Sciences. 2000. V. 60, P. 442-464.

4[Mu2] Muchnik An. A. Conditional complexity and codes. // Theoretical Computer Science. 2002. V. 271(1-2), P. 97-109.

но будет сказать, что алгоритмическая теория информации является более тонким инструментом, чем шенноновская (платой за это является ее асимптотичность). Мы показываем, что это так на примере известной теоремы Вольфа-Слепяна из классической теории информации, аналог которой (Теорема 3) перестает быть верным с большей точностью (Теорема 4).

Вторая тема настоящей работы связана с определением понятия информационного расстояния между двумя конечными объектами. Ч. Беннетт, П. Гач, М. Ли, П. Витаньи и В. Цурек в статье [BGLVZ]5, посвященной этому вопросу, рассматривают различные определения этого понятия. Одним из этих определений является длина кратчайшей программы, переводящей первый объект во второй, а второй - в первый. Авторы показывают, что всегда можно найти пару кратчайших программ, переводящих первый объект во второй, и второй - в первый соответственно, максимально "перекрывающихся", т.е. имеющих максимально возможную общую информацию (это означает, что более короткая из этих программ "содержится" в более длинной) в очень сильном смысле. В связи с этим авторы ставят вопрос о минимальном перекрытии: всегда ли найдутся абсолютно независимые (имеющие нулевую общую информацию) кратчайшие программы, переводящие первый объект во второй, и второй - в первый, соответственно?

В настоящей работе дается полный ответ на этот вопрос (Теорема 1 и Теорема 2). А именно, этот вопрос имеет положительный ответ с точностью до аддитивного члена порядка логарифма сложностей объектов (Теорема 2). Ответ становится отрицательным с точностью до аддитивного члена порядка логарифма условных сложностей (Теорема 1).

Далее, в данной работе также рассматривается вопрос о существовании "неделимых" объектов, т.е. таких, для разделения которых на нетривиальные части требуется значительная дополнительная информация. Доказано, что такие объекты существуют и найдена точная нижняя оценка для их сложности (Теорема 5).

'[BGLVZ] Bennett С.Н., Gdcs Р., Li М., Vitinyx Р., and Zurtk W.H. Information Distance. // IEEE TVans. on Information Theory 44 (1998), No 4,1407-1423.

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

Последняя тема настоящей работы связана со следующим вопросом. Пусть даны два слова х и у и программа р, которая получив на вход х, выдает у. Пусть эта программа не является кратчайшей среди всех программ, переводящих х в у. Хотелось бы узнать, всегда ли можно найти более короткую программу р', также переводящую х в у., простую при известной программе р. Существование такой р' означало бы "упрощаемость" программы р, т.е. этот вопрос можно назвать вопросом о существовании "неупрощаемых" программ. Мы доказываем, что такие примеры существуют (Теорема 5). Приводятся различные доказательства этого факта.

Цель работы. Основной целью данной работы является исследование вопросов о существовании наборов конечных объектов, удовлетворяющих заданным информационным соотношениям (различной точности), сформулированным в терминах алгоритмической теории информации. В частности, решить поставленный в [BGLVZ] вопрос о существовании независимых программ, переводящих два объекта друг в друга, а также провести анализ степени точности выполнения алгоритмического аналога теоремы Вольфа - Слепяна (из классической теории информации).

Методы исследования. В работе применяются методы теории алгоритмов и игровые методы.

Научная новизна. Все основные результаты работы являются новыми и состоят в следующем:

1. Исследован вопрос о существовании независимых программ, переводящих конструктивные объекты друг в друга. Решена задача о минимальном перекрытии, поставленная в

2. Получена нижняя оценка для точности, с которой выполнен алгоритмический аналог теоремы Вольфа-Слепяна из классической теории информации.

3. Доказано существование объектов, деление которых на нетривиальные части требует большой дополнительной информации ("неделимых" объектов).

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

5. Доказано существование избыточных по длине программ, которые не задают более короткой программы, решающей ту же задачу ("неупро-щаемых" программ).

Теоретическая и практическая ценность. Работа носит теоретический характер. Полученные результаты относятся к теории колмогоров-ской сложности и могут применяться в алгоритмической теории информации.

Апробация работы. Основные результаты настоящей диссертации докладывались на следующих семинарах и конференциях:

♦ научно-исследовательском семинаре по математической логике в МГУ под руководством академика РАН проф. С. И. Адана и проф. В. А. Успенского;

♦ семинаре "Колмогоровский семинар по сложности вычислений и сложности определений" под руководством Н. К. Верещагина, А. Л. Семенова, А. X. Шеня и А. Е. Ромащенко;

♦ международной конференции 15th Annual IEEE Conference on Computational Complexity в 2000 г;

♦ конференции "Ломоносовские чтения" в МГУ им. М. В. Ломоносова в 2000 г;

♦ XXII Конференции молодых ученых механико-математического факультета МГУ им. М. В. Ломоносова в 2000 г;

♦ XXI Конференции молодых ученых механико-математического факультета МГУ им. М. В. Ломоносова в 1999 г.

Публикации. Основные результаты диссертации опубликованы в четырех работах, указанных в конце автореферата.

Структура работы. Работа состоит из введения, 4 глав, списка используемых обозначений и списка литературы, содержащего 15 наименований. Общий объем диссертации - 71 страница.

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

Содержание работы

Во введении дан краткий обзор работ, связанных с темой диссертации, и сформулированы основные результаты диссертации.

Колмогоровская, или алгоритмическая, сложность слов была введена в 1965 году в работе А. Н. Колмогорова [Koll]. Пусть а; и у - двоичные слова (конечные последовательности нулей и единиц). Неформально, кол-могоровская сложность относительно определяется как длина самой короткой программы, которая получая на вход слово , выдает слово .

Будем называть способом программирования любую частичную вычислимую функцию двух аргументов А (аргументы и значения А - двоичные слова). Значение А(р,х) будем интерпретировать как результат работы программы р на входе х. Если А{р,х) не определено, то будем говорить, что при способе программирования А программа р на входе х не выдает никакого результата. Теперь мы можем определить колмогоровскую сложность слова у относительно слова х при способе программирования А как:

Надо обратить внимание на то, что определяемая таким образом сложность зависит от выбора способа программирования. Важным открытием Колмогорова стало существование оптимального способа программирования. Сформулируем данное утверждение точно. Будем говорить, что способ программирования А не хуже, чем способ программирования В, если

Согласно [Ко11] существует оптимальный способ программирования, т. е. способ программирования £Л который не хуже любого другого.

Оптимальный способ программирования не единствен. Если Щ и 11\ два оптимальных способа программирования, то они отличаются лишь на ограниченную величину:

min |р| , если существует такое р, что А(р, х) = у , (р,х)=у

оо , если нет такого р, что А(р, ®) = у

3С V®, у КА(у\х) < Кв{уИ + с.

3С Vx.y I KVl(yI®) - ЗДу|г) |< С,

т. е. асимптотически колмогоровские сложности относительно разных оптимальных способов программирования ведут себя одинаково. Некоторые оптимальные способы программирования могут иметь те или иные особые свойства. Однако в данной работе мы не будем интересоваться различиями между оптимальными способами программирования. Поэтому мы можем зафиксировать любой из них (назовем его £/"). В дальнейшем будем рассматривать только колмогоровскую сложность относительно выбранного оптимального способа программирования: Кц{у\х). При этом мы будем опускать индекс , т. е. будем пользоваться обозначением

Величину К(у|х) будем называть колмогоровской сложностью слова у относительно слова X (или колмогоровской сложностью слова у при известном слове х). Заметим, что для любых х, у условная сложность /£"(у|х) конечна.

Колмогоровской сложностью слова х назовем сложность х относительно пустого слова. Колмогоровскую сложность х будем обозначать К(х):

К{х) := К{х\\)

Кроме колмогоровской сложности слов будем рассматривать колмо-горовскую сложность кортежей слов. Для этого мы должны выбрать некоторую вычислимую нумерацию всех кортежей слов, т. е. вычислимую биекцию между множеством всех кортежей двоичных слов и множеством двоичных слов. В выборе такой нумерации, так же как и в выборе оптимального способа программирования, имеется значительный произвол. Зафиксировав некоторую нумерацию кортежей, назовем колмогоровской сложностью кортежа слов (у\,... ,уп) относительно кортежа слов (х1,...,хт) колмогоровскую сложность номера первого кортежа относительно номера второго кортежа. Данную сложность мы будем обозначать К(У1, Уп|^1) • • • > Хт). Ясно, что смена нумерации кортежей изменит колмогоровские сложности кортежей лишь на ограниченную величину.

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

нумерацию данных объектов. При этом изменение нумерации приведет к изменению колмогоровских сложностей рассматриваемых объектов лишь на ограниченную величину. Говоря о колмогоровской сложности тех или иных конструктивных объектов, мы всегда будем подразумевать, что для них зафиксирована некоторая вычислимая нумерация.

Взаимная информация слов х и у определяется как разность между суммой колмогоровских сложностей слов х и у и колмогоровской сложностью пары (х,у)\

7(х:у):= К(х) + К(у) - К(х,у).

Необходимо отметить, что данное определение отличается от оригинального определения Колмогорова (они равносильны с точностью до аддитивного члена вида 0(logK(x, у)), однако не до 0(1(х : у))). Взаимная информация х и у показывает, насколько знание одного из этих слов упрощает задачу нахождения другого.

Назовем слова х и у независимыми если их взаимная информация 1(х : у) близка к 0. Это определение неформально и в каждом конкретном случае необходимо уточнять понимание "близости".

Перечисление других свойств колмогоровской сложности и взаимной информации можно найти в или

Договоримся называть слово х случайным или несжимаемым если его колмогоровская сложность К{х) близка к ¿(¡с) где £(х) длина х.. Это определение неформально и нуждается в уточнении в каждом случае. Оно отвечает интуитивному пониманию случайности так как большинство слов любой фиксированной длины случайны в смысле этого определения.

На этом мы закончим необходимый обзор теории колмогоровской слож-. ности и перейдем непосредственно к теме данной работы.

Результаты настоящей работы можно разделить на несколько групп.

Главной темой Главы 1 является рассмотрение вопросов, связанных с понятием информационного расстояния.

Колмогоровская сложность является общепринятой мерой количества информации, содержащегося в индивидуальном конструктивном объекте. Хотелось бы определить подобную же меру для информационного расстояния между двумя объектами. Ч. Беннетт, П. Гач, М. Ли, П. Витаньи и

•[LVJ Li М., Vitdnyi P. An Introduction to Kolmogorov Complexity and its Applications. // Springer Verlag, 1997.

T[ZvLe] Звонки» А.К., Левин Л.А. Сложность конечных объектов и обоснование понятий • информации н случайности с помощью теории алгоритмов. // УМН. 1970. Т. 25, номер б, С. 85-127.

В. Цурек в статье [BGLVZ] рассматривают несколько естественных определений меры информационного расстояния и доказывают, что эти определения эквивалентны в сильном смысле.

Интуитивно, информационное расстояние между словами х и у равно минимальному количеству информации, достаточному для того, чтобы вычислимо по х восстановить у и наоборот, вычислимо по у восстановить х. Чтобы быть расстоянием, такая мера D(x,y) должна удовлетворять аксиомам:

если и только если ;

(неравенство треугольника);

• D(x, у) = D{y, х) (симметричность).

Следуя [BGLVZJ, рассмотрим две возможные формализации этого понятия. Первой естественной мерой информационного расстояния между словами х и у является длина кратчайшей программы, которая получая на вход х, дает у и, обратно, получая на вход у, дает х.. Обозначим эту меру di{x,y)

Указанная кратчайшая программа должна воспользоваться имеющейся избыточностью информации, необходимой для перехода от ж к у иин-формации, необходимой для перехода от к (т.е. их "общей частью"). Хотелось бы знать, в каких пределах информация, необходимая для перехода от х к у может быть выбрана "перекрывающейся" с информацией, необходимой для перехода от к . В некоторых простых случаях может быть достигнуто полное перекрытие так, что одна и та же кратчайшая программа позволяет переходить как от хк у„ так и наоборот. Например, если х и у - независимые случайные слова одинаковой длины п (с точностью до аддитивной константы К(х\у) = К(у\х) = ri), то их побитовое исключающее "или" х ® у является искомой кратчайшей программой для обоих вычислений ( при известном и при известном ).

Рассмотрим теперь случай когда одно из этих вычислений требует больше информации, чем другое, например,

К(у\х) > К{х\у)

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

содержать всю информацию, содержащуюся в меньшей, наряду с некоторой дополнительной информацией.

Прежде чем сформулировать главный результат работы (BGLVZ], определим еще одну меру информационного расстояния между словами как

В дальнейшем информационным расстоянием мы будем именовать величину d(x,y). Очевидно, что с точностью до аддитивного члена вида выполнены неравенства

d(x,y) < di(x,y) < ВДу) + К{у\х) < 2d(x,y),

Можно было бы предполагать, что в худшем случае перекрытие оказывается нулевым, то есть достигается равенство di{x,y) = А"(х|у)+/Г(у|1)+ 0(\ogd(x,y)), причем К(х\у) + К(у\х) значительно превосходит d[i,y). Однако оказывается, что для любых слов х, у выполнено равенство

d\{x, у) = d(x,y) + 0(logd(x, у)).

Это утверждение является прямым следствием следующей теоремы. Теорема о преобразовании [BGLVZ]. Пусть слова ®,у таковы, что Я"(у|х) > if(l|y). Тогда найдутся слово d длины К(у\х) — if(x|y) и программа Г длины К(х\у) + 2К{(К{х\у), + 0(1), которая получив на вход xd дает у и обратно, получив на вход у дает xd.

Эта теорема утверждает существование кратчайших программ р и q, переводящих X в у,, а у в X соответственно, "перекрывающихся" максимальным возможным способом. Действительно, имея р = (г, ¿(d)) и у, мы можем вычислить , а имея и мы вычислим .

В настоящей работе мы рассмотрим противоположный вопрос: всегда ли упомянутые кратчайшие программы р и q могут быть выбраны полностью независимыми, а именно, такими что взаимная информация 1(р : q) близка к нулю. То есть, правда ли, что для каждой пары слов Х,у найдутся программы ри q такие, что U(p, х) = у, U(q, у) = х, £(р) m К(у\х), £(q) pu К[х\у) и 1(р : <7) ~ 0 (где приблизительные равенства выполнены с точностью до аддитивного члена вида O(logd(x, у)))? Эта задача была поставлена в

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

Теорема 1. Для любого d найдется с такое, что для всех п выполнено следующее. Существуют слова х, у такие, что

п < К(х\у), К(у\х) < п + 2 log log n + с

и для всех слов р, q с длинами менее n + d log п и таких, что U(р, х) = у, ^(9>У) ~ х, выполнено неравенство

Я) < п + (2d+ 7) log п + с.

Однако, если потребовать чтобы равенства ¿(р) и iC(i/|x), ¿(9) « К"(х|у), I(p : q) и 0 выполнялись с точностью до аддитивного члена вида (вместо O(logd(x,y))}, ситуация изменится кардинальным образом. В этом случае всегда найдется пара независимых программ Р,Я

Теорема 2. Для любых двух слов х, у найдутся программы р и q такие, что U(p, х) ~ у, U(q,y) = х, t{p) « К(у\х), i(q) « К(х\у), и 1(р :?)и0

(где приблизительные равенства выполнены с точностью до аддитивного члена вида 0(log К(х,у))).

В Разделе 1.4 мы рассмотрим вопрос о связи между шенноновской и алгоритмической теориями информации.

Между шенноновской теорией информации и теорией колмогоровской сложности имеется сильный параллелизм. Некоторые теоремы шенноновской теории информации имеют аналоги в теории колмогоровской сложности (см. например [Ко12]8, [HRSV], [Muí]). Одним из таких результатов является следующая теорема, доказанная Ан. А. Мучником.

Теорема 3 (Ан. А. Мучник). Для любых слов х и у найдется слово р такое, что

Op) « К(у\х), (1)

К(у\х,р) и 0, (2)

(3) K{j>\y) « О,

где приблизительные равенства выполняются с точностью до аддитивного члена вида 0(logK"(y)).

*[KoI2] Колмогоров А.Н. Комбинаторные основания теории информации и исчисления вероятностей. // УМН. 1983. Т. 38, номер 4, С. 27-36.

То есть для любой пары слов Х,у найдется кратчайшая программа р, переводящая х в у, простая относительно у.

Эта теорема является прямым аналогом теоремы Вольфа-Слепяна из шенноновской теории информации [KoCs]9

Однако Теорема 3 бессодержательна (т.е. очевидна) в случае когда слова а и у отличаются мало, например когда К{у\х) имеет порядок 0(log.if(y)). Хотелось бы узнать, можно ли усилить теорему так, чтобы приблизительные равенства выполнялись с большей точностью, зависящей только от

К(у\х)

В настоящей работе мы даем отрицательный ответ на этот вопрос. А именно, верна следующая

Теорема 4. Теорема 3 перестает быть верной, если потребовать выполнения приблизительных равенств (1)~(3) с точностью до аддитивного члена вида OQogK(y\x))

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

В Главе 2 рассматривается вопрос о "разделении"информации.

Рассмотрим следующий вопрос. Зафиксируем числа а и /? такие, что а>0, /3>0иа + /?=1. Можно ли произвольное слово х разделить в пропорции а : /3? Формально это означает: верно ли, что для любого слова найдется слово такое, что

К(у) « аК(х), К{х\у) « рК{х).

Этот вопрос, как и предыдущие, имеет разные варианты в зависимости от желаемой степени точности. Легко видеть, что с точностью до O(logif(x,y)) ответ положителен. Достаточно перейти от слова X к кратчайшей программе, вычисляющей х и взять в качестве у начальный кусок этой программы длины аК[х). Можно было бы предположить, что результат остается верным и при точности 0(1), однако это не так. Из следующей теоремы следует отрицательный ответ при точности j log log/Г (х)

•[KoCs] Чисор И., Кернер Я. Теория информации. Теоремы кодирования для дискретных систем без памяти. // М.: Мир. 1985.

Теорема 5. Существует константа с > 0 такая, 'что для любого натурального числа к существует слово х такое, что К(х) > 3к, и удовлетворяющее условию: для любого слова у, если К(у\х) < к, то либо

либо

К{х\у) <к + с.

Длина слова X равна 3£22'. При этом, существует константа с\ такая, что для каждого х удовлетворяющего вышеприведенному условию, выполнено

К(х) > 22'"4

Число таких X -ов конечно.

Эта теорема утверждает существование слова х, неделимого ни в какой пропорции. Любое слово у, простое относительно х либо просто абсолютно, либо мало отличается от х. Она также дает нижнюю оценку на сложность такого примера.

В Главе 3 мы рассмотрим следующий общий вопрос. Для данного слова XQ мы хотим подобрать слова Хх,Х2,... ,хт так, чтобы набор слов Хо,Х\,...,Хт удовлетворял заранее заданным информационным соотношениям. В общем виде такой вопрос очень сложен и мы дадим ответы на некоторые из его частных случаев.

Начнем со следующего частного вопроса. Верно ли, что для всякого числа и слова такого, что можно найти слово у для которого

К(х\у)яп,К(у\х)ъп. (4)

Легко доказать, что с точностью до аддитивного члена вида ответ на этот вопрос положителен, такое слово у всегда найдется. Но можно ли усилить это утверждение? В отличие от приведенных выше случаев, это сделать можно для точности OQog п), а в большинстве случаев даже до 0(1). А именно верна следующая

Теорема б. Существует константа с такая, что для любого п выполнено следующее: для любого слова х удовлетворяющего условию К(х) > 2п + С. найдется слово у такое, что обе условные сложности /С(аг|у) и А"(у|х) располагаются между п и п + С

п<К(х\у),К(у\х)<п + с.

Эта теорема не покрывает случая п < К(х) < 2п„ в котором однако можно применить упомянутое выше утверждение с точностью О(\0£К(х)) и получить результат с точностью 0(1с^п).

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

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

Теорема 7. Для каждого числа т найдется константа с такая, что для всякого п и всякого двоичного слова Хо такого, что К{хо) > П выполнено • следующее: существует набор слов Ху,... ,Хт удовлетворяющий условию

\Kixi\ij) - п| < 51о§п + с, 0 < г, 3 <т^ф 3.

Можно также изучить возможность дальнейшего усиления этого результата. В случае трех слов легко доказать следующую простую теорему.

Теорема 8. Пусть даны число п и слово Хо такие, что К{хо) > п. Тогда, найдутся слова XI и Х2 такие, что

К{хг\х,, хк) и п, »',к £ {0,1,2},» ф 3 ф к, г ф к,

где приблизительные равенства выполнены с точностью до аддитивного члена вида 0(logJf(xo))

Встает вопрос: можно ли ее усилить, потребовав точности 0(^п)'? Из следующей теоремы следует отрицательный ответ на этот вопрос.

Теорема 9. Существует константа с, для которой выполнено следующее. Пусть Пи <1 - произвольные целые числа. Существует слово Хо такое, что К{хо) >П + с1 и нет слов XI и Хг, удовлетворяющих следующим неравенствам:

К{яц\хЦ < п + Л,»,з € {0,1,2}, г ф з, К(х0\х{)>с1 + 2\о5п + с)И={1,2},

Глава 4 посвящена изучению вопроса о существовании "неупрощае-мых" программ. Пусть нам дана некоторая программар которая, получая

на вход слово х, выдает результат у. Нам хотелось бы найти другую программу р* с тем же свойством (на входе х выдавать у), имеющую меньшую колмогоровскую сложность. Мы также требуем чтобы р' легко получалась по р, т.е. чтобы колмогоровская сложность К{][/\р) была мала. Заметим, что когда мы говорим о программах, можно вместо колмогоровской сложности говорить о длине: р можно заменить на кратчайшую программу, вычисляющую р.. Мы показываем что в некоторых случаях такой программы р* не существует, даже если длина р намного превышает условную сложность К{у\х).. Это следует из следующей теоремы.

Теорема 10. Существуют такие константы < с2 < Сз„ а также с и £ > 0, что для всякого натурального п найдутся слова Х,у,р со следующими свойствами:

(a) К(у | Х,р) < (слово р является описанием у при известном х с логарифмической точностью);

(b) К(у | х) < ап (сложность у при известном X мала...);

(¡1) не существует слова р*, для которого < СгЯ, | р) < £П и

К(у \ Х,р?) < £П (...но не существует описания р', упрощающего р до промежуточной сложности С2П).

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

Этот результат можно проинтерпретировать и другим способом. Будем называть слово р описанием слова у при известном х, если колмогоровская сложность К(у\х,р) близка к нулю (насколько близка, нужно в каждом случае уточнять отдельно). Для данных х и у будем рассматривать всевозможные описания у при известном х.. Очевидно, каждое из них имеет длину и сложность не меньше К(у\х) и что эта оценка достигается (с точностью всюду 0(1о§п) где п - наибольшая сложность рассматриваемых слов).

Назовем описание р' упрощением описания р если А"(р'|р) яз 0 (с той же точностью). Это отношение можно считать (с неизбежными оговорками про точность) частичным порядком, и представляет интерес структура множества всех описаний (для данных 1и у) относительно этого порядка.

Среди описаний, естественно, имеется и само слово у. Приведенная выше Теорема 3 (из [Ми2]), утверждает что существует описание минимальной длины, являющееся упрощением у.. Теорема 10 показывает что для произвольного описания это уже не так. Существует описание р, имеющее сложность много больше К(у\х), но не имеющее упрощений существенно меньшей сложности.

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

Публикации автора по теме диссертации

[1] Вьюгин М.В. Информационное расстояние и условная сложность. // Труды XXII конференции молодых ученых мех.-мат. факультета МГУ. С. 40-41. Москва, 2001.

[2] Vereshchagin N., Vyugin M.V. Independent minimum length programs to translate between given strings. // Theoretical Computer Science 271(1-2):P.131-143. 2002.

[3] Vyugin M.V. Information distance and conditional complexities. // Theoretical Computer Science 271(1-2): P.145-150. 2002.

[4] Вьюгин М.В. Системы слов с большой взаимной сложностью. // Проблемы передачи информации. 2003. Т. 39, номер 4, С. 88-92.

Издательство ЦПИ при механико-математическом факультете МГУ им. М.В. Ломоносова,

Подписано в печать ОЗ. 2

Формат 60x90 1/16. Усл. печ. л. /,0

Тираж /Ьсэкз. Заказ JZjf

Лицензия на издательскую деятельность ИД В 04059, от 20.02.2001г.

Отпечатано с оригинал-макета на типографском оборудовании механико-математического факультета и Франко-русского центра им. A.M. Ляпунова.

р- 764 2

Содержание диссертации автор исследовательской работы: кандидата физико-математических наук, Вьюгин, Михаил Владимирович

Введение

1 Информационное расстояние

1.1 Минимальное перекрытие с точностью до 0(log К(х, у)).

1.2 Конденсация информации.

1.3 Минимальное перекрытие с точностью до 0(\ogd(x, у)).

1.4 Шенноновская и алгоритмическая теории информации

2 Неделимые слова

3 Системы слов с большой взаимной сложностью

3.1 Положительный результат

3.2 Точность положительного результата.

3.3 Еще одна попытка обобщить основной результат.

4 Неупрощаемые программы

4.1 Игровой подход.

4.2 Вероятностный подход.

Используемые обозначения

Введение диссертация по математике, на тему "Наборы конечных объектов с заданными информационными соотношениями между ними"

Актуальность темы. А. Н. Колмогоров в работе [1] выделил три похода к определению понятия "количество информации": комбинаторный, вероятностный и алгоритмический. Вероятностный подход основан на понятии энтропии Шеннона тогда как алгоритмический - на введенном Колмогоровым понятии алгоритмической сложности. Классическая теория информации Шеннона рассматривает случайные величины, в то время как алгоритмическая теория информации Колмогорова имеет дело с индивидуальными объектами. Тем не менее, многие утверждения могут, после соответствующей переформулировки, быть перенесены из первой теории во вторую (примеры можно найти в работах [8], [11]; также см. Теорему 1.6, приведенную далее, доказанную Ан. А. Мучником и опубликованную в [9]). Получающиеся аналоги, как и все результаты теории алгоритмической сложности, имеют асимптотический характер и выполнены лишь с определенной точностью. Наилучшая возможная точность - до аддитивной константы. Однако большинство известных результатов вышеописанного типа выполнены с точностью до аддитивного члена порядка логарифма алгоритмической сложности рассматриваемых объектов.

Конечные объекты естественным образом отождествляются со своими конструктивными представлениями. Поэтому в дальнейшем мы будем говорить о конструктивных объектах.

В настоящей работе нас интересует вопрос о том, выполнены ли эти аналоги с большей точностью. Это становится существенным, если мы интересуемся сложными объектами, которые мало (по сравнению со своей сложностью) отличаются друг от друга. Если нам все же важно количество информации, необходимое для преобразования одного из этих объектов в другой, необходимо более тонкое рассмотрение, а именно рассмотрение с точностью до аддитивного члена, зависящего от условной алгоритмической сложности.

Если упомянутые алгоритмические аналоги теорем классической теории информации перестают быть верными с большей точностью, можно будет сказать, что алгоритмическая теория информации является более тонким инструментом, чем шенноновская (платой за это является ее асимптотичность). Мы показываем, что это так на примере известной теоремы Вольфа-Слепяна из классической теории информации, аналог которой (Теорема 1.6) перестает быть верным с большей точностью (Теорема 1.7).

Вторая тема настоящей работы связана с определением понятия информационного расстояния между двумя конечными объектами. Ч. Беннетт, П. Гач, М. Ли, П. Витаньи и В. Цурек в статье [5], посвященной этому вопросу, рассматривают различные определения этого понятия. Одним из этих определений является длина кратчайшей программы, переводящей первый объект во второй, а второй - в первый. Авторы показывают, что всегда можно найти пару кратчайших программ, переводящих первый объект во второй, и второй - в первый соответственно, максимально "перекрывающихся", т.е. имеющих максимально возможную общую информацию (это означает, что более короткая из этих программ "содержится" в более длинной) в очень сильном смысле. В связи с этим авторы [5] ставят вопрос о минимальном перекрытии: всегда ли найдутся абсолютно независимые (имеющие нулевую общую информацию) кратчайшие программы, переводящие первый объект во второй, и второй - в первый, соответственно?

В настоящей работе дается полный ответ на этот вопрос (Теорема 1.5 и Теорема 1.1). А именно, этот вопрос имеет положительный ответ с точностью до аддитивного члена порядка логарифма сложностей объектов (Теорема 1.1). Ответ становится отрицательным с точностью до аддитивного члена порядка логарифма условных сложностей (Теорема 1.5).

Следующим рассмотрен вопрос о существовании для данного фиксированного объекта такого конечного набора других объектов, который вместе с исходным объектом удовлетворял бы заранее заданному набору информационных соотношений. Этот вопрос, как и предыдущие, имеет два варианта - в зависимости от желаемой степени точности. Мы рассматриваем один частный случай данного вопроса. В этом частном случае с высокой точностью выполнен положительный результат (Теорема 3.2, а также Теорема 3.3). Мы также доказываем некоторые утверждения о невозможности усиления положительного результата в различных направлениях (разделы 3.2 и 3.3).

Последняя тема настоящей работы связана со следующим вопросом. Пусть даны два слова х и у и программа р, которая получив на вход х, выдает у. Пусть эта программа не является кратчайшей среди всех программ, переводящих х в у. Хотелось бы узнать, всегда ли можно найти более короткую программу р', также переводящую х в у, простую при известной программе р. Существование такой р' означало бы "упрощаемость" программы т.е. этот вопрос можно назвать вопросом о существовании "неупрощаемых" программ. Мы доказываем, что такие примеры существуют (Теорема 4.1). Приводятся различные доказательства этого факта.

Методы исследования. В работе применяются методы теории алгоритмов и игровые методы.

Научная новизна. Все основные результаты работы являются новыми и состоят в следующем:

1. Исследован вопрос о существовании независимых программ, переводящих конструктивные объекты друг в друга. Решена задача о минимальном перекрытии, поставленная в [5].

5. Доказано существование избыточных по длине программ, которые не задают более короткой программы, решающей ту же задачу ("неупрощаем ых" программ).

Приложения. Работа носит теоретический характер. Полученные результаты относятся к теории колмогоровской сложности и могут применяться в алгоритмической теории информации.

• научно-исследовательском семинаре по математической логике в МГУ под руководством академика РАН проф. С. И. Адяна и проф. В. А. Успенского;

• семинаре "Колмогоровский семинар по сложности вычислений и сложности определений" под руководством Н. К. Верещагина, А. Е. Ромащенко, A. JI. Семенова и А. X. Шеня;

• международной конференции 15th Annual IEEE Conference on Computational Complexity в 2000 г;

• конференции "Ломоносовские чтения" в МГУ им. М. В. Ломоносова в 2000 г;

• XXII Конференции молодых ученых механико-математического факультета МГУ им. М. В. Ломоносова в 2000 г;

• XXI Конференции молодых ученых механико-математического факультета МГУ им. М. В. Ломоносова в 1999 г.

Публикации. Основные результаты диссертации опубликованы в работах [12, 13, 14, 15].

Для полноты изложения в диссертации приводятся без доказательств Теорема 1.6 и Теорема о преобразовании, не принадлежащие автору. Первый из этих результатов получен Ан. А. Мучником и опубликован в работе [9]. Второй результат получен Ч. Беннетом, П. Гачем, М. Ли, П. Витаньи и В. Цуреком и опубликован в работе [5]. Также в главе 4 приведено вероятностное доказательство Теоремы 4.1, принадлежащее Ан. А. Мучнику.

Список источников диссертации и автореферата по математике, кандидата физико-математических наук, Вьюгин, Михаил Владимирович, Москва

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

2. Колмогоров А.Н. Комбинаторные основания теории информации и исчисления вероятностей. / / УМЫ. 1983. Т. 38, номер 4, 27-36.

3. Чисар И., Кернер Я. Теория информации. Теоремы кодирования для дискретных систем без памяти. / / М.: Мир. 1985.

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

5. Bennett Н., Gacs P., Li М., Vitanyi P., and Zurek W.H. Information Distance.// IEEE Trans, on Information Theory 44 (1998), No 4, 1407-1423.

6. Gorbunov K.Yu. On a Complexity of the Formula (АУ B) —> C. / / Theoretical Computer Science, 207(2) (1998), 383-386.

7. Li M., Vitanyi P. An Introduction to Kolmogorov Complexity and its Applications. / / Springer Verlag, 1997.

8. Muchnik An.A. On Common Information. / / Theoretical Computer Science. 1998. V. 207, P. 319-328

9. Muchnik An.A. Conditional complexity and codes. / / Theoretical Computer Science. 2002. V. 271(1-2), P. 97-109.

10. Uspensky V.A., Shen A. Relations between varieties of Kolmogorov complexities. / / Mathematical system theory. 1996. V. 29, No. 3, P. 271-292. Литература 71

11. Hammer D., Romashchenko A., Shen A., Vereshchagin N. InequaUties for Shannon Entropy and Kolmogorov Complexity. / / Journal of Computer and System Sciences. 2000. V. 60, P. 442-464.

12. Вьюгин M.B. Информационное расстояние и условная сложность. / / Труды XXII конференции молодых ученых мех.-мат. факультета МГУ. Москва, 2001. 40-41.

13. Vereshchagin N., Vyugin M.V. Independent minimum length programs to translate between given strings. / / Theoretical Computer Science 271(1-2):131-143, 2002.

14. Vyugin M.V. Information distance and conditional complexities. / / Theoretical Computer Science 271(1-2): 145-150 (2002)

15. Вьюгип M.B. Системы слов с большой взаимной сложностью. / / Проблемы передачи информации. 2003. Т. 39, Вын. 4, 88-92.