Сложность Колмогорова: Алгоритмическая мера информации

Введение

В алгоритмической теории информации (подраздел информатики и математики) сложность Колмогорова объекта, например фрагмента текста, — это длина кратчайшей компьютерной программы (на заранее определенном языке программирования), которая выдает этот объект в качестве результата. Это мера вычислительных ресурсов, необходимых для задания объекта, также известная как алгоритмическая сложность, сложность Соломонова — Колмогорова — Чайтина, сложность по размеру программы, описательная сложность или алгоритмическая энтропия. Она названа в честь Андрея Колмогорова, который впервые опубликовал работы на эту тему в 1963 году, и является обобщением классической теории информации. Понятие сложности Колмогорова можно использовать для формулировки и доказательства результатов невозможности, аналогичных диагональному аргументу Кантора, теореме Гёделя о неполноте и проблеме останова Тьюринга. В частности, ни одна программа P, вычисляющая нижнюю границу сложности Колмогорова для каждого текста, не может вернуть значение, существенно превышающее собственную длину P (см. раздел); следовательно, ни одна программа не может вычислить точную сложность Колмогорова для бесконечного числа текстов.

Равнина Колмогорова сложности C

Существует два определения сложности Колмогорова: простое и без префикса. Простая сложность – это минимальная длина описания любой программы, обозначаемая , а сложность без префикса – это минимальная длина описания любой программы, закодированной кодом без префикса, обозначаемая . Простая сложность более интуитивно понятна, но сложность без префикса легче изучать. По умолчанию все уравнения верны лишь с точностью до аддитивной константы. Например, на самом деле означает, что , то есть, .
Пусть – вычислимая функция, отображающая конечные двоичные строки в двоичные строки. Она является универсальной функцией тогда и только тогда, когда для любой вычислимой функции мы можем закодировать эту функцию в "программу" , такую что . Мы можем рассматривать как интерпретатор программы, который принимает на вход начальный сегмент, описывающий программу, а затем данные, которые программа должна обработать. Одна из проблем простой сложности заключается в том, что , поскольку интуитивно нет общего способа определить, где разделить выходную строку, просто взглянув на конкатенированную строку. Мы можем разделить её, указав длину или , но это потребует дополнительных символов. Действительно, для любого существует такое , что .
Обычно в неравенствах с простой сложностью присутствует член, например, в одной из сторон, в то время как те же неравенства со сложностью без префикса содержат только .
Основная проблема простой сложности заключается в том, что в программу "проникает" дополнительная информация. Программа представляет что-то своим кодом, но также и свою собственную длину. В частности, программа может представлять двоичное число до , просто своей длиной. Иными словами, это как если бы мы использовали символ завершения, чтобы обозначить конец слова, и, следовательно, использовали не 2 символа, а 3. Чтобы устранить этот недостаток, мы вводим сложность Колмогорова без префикса.

История и контекст

Алгоритмическая теория информации — это область компьютерных наук, изучающая сложность Колмогорова и другие меры сложности для строк (или других структур данных). Концепция и теория сложности Колмогорова основаны на ключевой теореме, впервые обнаруженной Рэем Соломоноффом, который опубликовал её в 1960 году, описав в «Предварительном отчёте об общей теории индуктивного вывода» как часть своего изобретения — алгоритмической вероятности. Более полное описание он дал в своих публикациях 1964 года «Формальная теория индуктивного вывода», части 1 и 2 в журнале «Information and Control». Позже Андрей Колмогоров независимо опубликовал эту теорему в «Проблемах передачи информации» в 1965 году. Грегори Чайтин также представляет эту теорему в журнале J. ACM — статья Чайтина была представлена в октябре 1966 года и пересмотрена в декабре 1968 года, с ссылками на работы Соломоноффа и Колмогорова. Теорема утверждает, что среди алгоритмов, декодирующих строки из их описаний (кодов), существует оптимальный. Этот алгоритм для всех строк позволяет коды, не длиннее, чем те, что допускаются любым другим алгоритмом, с точностью до аддитивной константы, зависящей от алгоритмов, но не от самих строк. Соломонофф использовал этот алгоритм и длины кодов, которые он позволяет, для определения «универсальной вероятности» строки, на основе которой может быть построен индуктивный вывод последующих символов строки. Колмогоров использовал эту теорему для определения нескольких функций строк, включая сложность, случайность и информативность. Когда Колмогоров узнал о работе Соломоноффа, он признал его приоритет. В течение нескольких лет работы Соломоноффа были более известны в Советском Союзе, чем в западном мире. Однако в научном сообществе сложилось общее мнение, что данный тип сложности следует связывать с Колмогоровым, который интересовался случайностью последовательностей, а алгоритмическая вероятность — с Соломоноффом, который сосредоточился на прогнозировании, используя изобретённое им универсальное априорное распределение вероятностей. Более широкая область, охватывающая описательную сложность и вероятность, часто называется сложностью Колмогорова. Компьютерный учёный Мин Ли считает это примером эффекта Мэтью: «Каждому, у кого есть, дано будет ещё больше». Существуют и другие варианты сложности Колмогорова или алгоритмической информации. Наиболее широко используемый из них основан на самоограничивающих программах и в значительной степени принадлежит Леониду Левину (1974). Аксиоматический подход к сложности Колмогорова, основанный на аксиомах Блума (Blum 1967), был предложен Марком Бургиным в статье, представленной для публикации Андреем Колмогоровым.

Algorithmic information theory is the area of computer science that studies Kolmogorov complexity and other complexity measures on strings (or other data structures). The concept and theory of Kolmogorov Complexity is based on a crucial theorem first discovered by Ray Solomonoff, who published it in 1960, describing it in "A Preliminary Report on a General Theory of Inductive Inference" as part of his invention of algorithmic probability. He gave a more complete description in his 1964 publications, "A Formal Theory of Inductive Inference," Part 1 and Part 2 in Information and Control. Andrey Kolmogorov later independently published this theorem in Problems Inform. Transmission in 1965. Gregory Chaitin also presents this theorem in J. ACM – Chaitin's paper was submitted October 1966 and revised in December 1968, and cites both Solomonoff's and Kolmogorov's papers. The theorem says that, among algorithms that decode strings from their descriptions (codes), there exists an optimal one. This algorithm, for all strings, allows codes as short as allowed by any other algorithm up to an additive constant that depends on the algorithms, but not on the strings themselves. Solomonoff used this algorithm and the code lengths it allows to define a "universal probability" of a string on which inductive inference of the subsequent digits of the string can be based. Kolmogorov used this theorem to define several functions of strings, including complexity, randomness, and information. When Kolmogorov became aware of Solomonoff's work, he acknowledged Solomonoff's priority. For several years, Solomonoff's work was better known in the Soviet Union than in the Western World. The general consensus in the scientific community, however, was to associate this type of complexity with Kolmogorov, who was concerned with randomness of a sequence, while Algorithmic Probability became associated with Solomonoff, who focused on prediction using his invention of the universal prior probability distribution. The broader area encompassing descriptional complexity and probability is often called Kolmogorov complexity. The computer scientist Ming Li considers this an example of the Matthew effect: " to everyone who has, more will be given "

There are several other variants of Kolmogorov complexity or algorithmic information. The most widely used one is based on self delimiting programs, and is mainly due to Leonid Levin (1974). An axiomatic approach to Kolmogorov complexity based on Blum axioms (Blum 1967) was introduced by Mark Burgin in the paper presented for publication by Andrey Kolmogorov.

Основные результаты

Мы пишем, что be, где означает некоторый фиксированный способ кодирования кортежа строк x и y.

Неравенства

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