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

• Автор: Вьюгин, Михаил Владимирович
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Москва
• Количество страниц: 71 с.

1 Информационное расстояние
1.1 Минимальное перекрытие с точностью
до 0(^Х(а;,у))
1.2 Конденсация информации
1.3 Минимальное перекрытие с точностью
до О(£с1(х,у))
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).
Далее, в данной работе также рассматривается вопрос о существовании “неделимых” объектов, т.е. таких, для разделения которых на нетривиальные части требуется значительная дополнительная информация. Доказано, что такие объекты существуют и найдена точная нижняя оценка для их сложности (Теорема 2.1).
Следующим рассмотрен вопрос о существовании для данного фиксированного объекта такого конечного набора других объектов, который вместе с исходным объектом удовлетворял бы заранее заданному набору информационных соотношений. Этот вопрос, как и предыдущие, имеет два ва
Глава 3. СИСТЕМЫ СЛОВ С БОЛЬШОЙ ВЗАИМНОЙ СЛОЖНОСТЬЮ

те ребра Природы, которые дублируют ребра Математика). Таким образом, после проведения последнего такого ребра, условие не изменится.
В Лемме 3.2 мы доказываем существование выигрывающей стратегии для Математика, вычислимой равномерно по п,т. Заметим, что эта стратегия выигрывает против любой (даже не вычислимой) стратегии Природы. Теперь, используя существование выигрывающей стратегии для Математика, получим утверждение теоремы.
Пусть Природа следует следующей стратегии. Она перечисляет все пары (х,у) такие, что К(ху) < п и когда она находит такую пару, то соединяет ж и у ребром, идущим из у в ж в каждой паре долей графа Х* и Xj, где i ф j.
Лемма 3.2 утверждает, что Математик выигрывает против указанной стратегии Природы. Это означает, что каждая неотмеченная вершина жо Е Х0, после достаточно большого числа ходов окажется соединена с каждой из вершин х Е Х,... ,хт Е Хт с условием: каждая пара (Xi,Xj) соединена Математиком и не соединена Природой.
Будем нумеровать ребра, исходящие из какой-либо вершины в том порядке, к каком они появились в игре.
Сначала убедимся, что вершины жо, которые были объявлены простыми, действительно просты. Для восстановления вершины жо, которая была отмечена в (ш, п)-той игре, достаточно знать т, п и номер жо среди всех элементов, отмеченных в этой игре. Мы также можем дополнить двоичную запись последнего числа нулями слева так, чтобы его длина оказалась равна log N. Тогда по этой записи мы сможем восстановить п зная т. Таким образом, мы можем задать жо словом длины logiV + 21ogm + 0(1).
Теперь мы знаем, что если жо удовлетворяет условию К{жо) > log N + 21ogm + 0(l), то оно не может быть отмечено в (т,п)-той игре. Возьмем любую такую вершину жо и соответствующие ей Ж1,... ,хт. Так как они не соединены Природой, то K(x{xj) п. Остается убедиться в том, что K(xixj) ненамного больше п.
Мы сделаем это тем же способом, который был использован для задания отмеченных вершин. Зададим вершину жг- Е Xj при известной вершине ж j Е Xj с помощью номера ребра Математика, соединяющего эти вершины среди всех ребер, соединяющих жj с вершинами из доли Xj. Затем дополним двоичную запись этого числа нулями слева так, чтобы длина этой записи оказалась равна п + 2 log т + 1.