В алгоритмической теории информации колмогоровская сложность объекта (текста, изображения...) есть длина наиболее короткого алгоритма, способного точно описать/сгенерировать объект. Известна также как описательная сложность, сложность Колмогорова — Хайтина, стохастическая сложность, алгоритмическая энтропия или алгоритмическая сложность.
К примеру, рассмотрим две строки длиной 64 символа:
abababababababababababababababababababababababababababababababab 4c1j5b2p0cv4w1x8rx2y39umgw5q85s7uraqbjfdppa0q7nieieqe9noc4cvafzf
Первая строка имеет простое описание на естественном языке, а именно ab 32 раза, состоящее из 10 символов. Вторая строка не имеет очевидного простого описания с использованием того же набора символов, кроме собственно самой этой строки, длина которой составляет 64 символа, поэтому колмогоровская сложность первой строки ниже, чем у второй.
Более формально, сложность строки — это длина описания этой строки на некотором универсальном языке описания. Способность сложности к изменению относительно выбора языка описания обсуждается ниже. Колмогоровская сложность любой строки не может быть более, чем на несколько байт больше, чем длина самой этой строки, так как программа может выглядеть как одна команда "напечатать строку", где строка указана в явном виде. Строки, чья колмогоровская сложность слабо зависит от размера самой строки, не считаются сложными.
Определение Чтобы определить колмогоровскую сложность, мы должны сначала задать язык описания строк. Такой язык описания может быть основан на любом языке программирования, таком как Lisp, Pascal или Java. Если — программа, выходом которой является строка , то — описание . Длиной описания является длина как строки. В ходе определения длины должны быть вычислены дли́ны подпрограмм, использующихся в . Длина любой целой константы , которая появляется в — это количество битов, требующихся для представления , равное (грубо) .
Мы можем альтернативно выбрать кодировку для машины Тьюринга, где кодировка — функция, устанавливающая в соответствие каждой машине Тьюринга битовую строку . Если — машина Тьюринга, которая на вход даёт на выходе строку , то объединённая строка есть описание для . Это теоретический подход, который является более подходящим для построения детальных формальных доказательств и предпочтителен в исследовательской литературе. Двоичное лямбда-исчисление может дать наиболее простое определение сложности. В этой статье мы используем неформальный подход.
Любая строка имеет как минимум одно описание, то есть программу
function GenerateFixedString() return s
Если описание , минимальной длины, то есть использует наименьшее количество символов, то оно называется минимальным описанием , а длина , то есть количество символов в этом описании, — колмогоровской сложностью , . Символьно:
Рассмотрим, как выбор языка описания влияет на значение , и покажем, что эффект от смены языка описания является ограниченным.
Теорема. Если и — функции сложности, относящиеся к языкам описания и , то существует константа (зависящая только от языков и ), такая, что
Доказательство. Обратно, достаточно доказать, что существует некоторая константа , такая, что для всех битовых строк
Положим, что существует программа на языке , которая работает как интерпретатор для :
function InterpretLanguage(string p)
где — программа на языке . Интерпретатор характеризуется следующим свойством: Возвращаемым значением в результате работы InterpretLanguage на входных данных будет результат работы .
Таким образом, если является программой на языке , которая является минимальным описанием , то InterpretLanguage() возвращает строку . Длина этого описания есть сумма: Длины программы InterpretLanguage, которая может быть принята за константу . Длины , определяемой . Это доказывает искомую верхнюю оценку.
История и контекст Алгоритмическая теория информации — это области компьютерной науки, изучающая колмогоровскую сложность и другие сложные меры для строк (или других структур данных).
Идея теории колмогоровской сложности основана на ключевой теореме, впервые открытой Рэем Соломоноффом (), опубликовавшим её в 1960 году, описав в работе «A Preliminary Report on a General Theory of Inductive Inference» revision , Nov., 1960. как часть своего изобретения алгоритмической вероятности. Он дал более полное описание в своих публикациях «A Formal Theory of Inductive Inference», часть 1 и 2 в журнале «Information and Control», сделанных в 1964 году.
Позже А. Н. Колмогоров независимо опубликовал эту теорему в журнале «Проблемы передачи информации», Грегори Хайтин также представил эту теорему в журнале «J. ACM». Работа Хайтина была отправлена в октябре 1966 года, исправлена в декабре 1968 года и цитирует обе работы Соломоноффа и Колмогорова.
Теорема утверждает, что среди алгоритмов, восстанавливающих (декодирующих) строки из их описаний (кодов) существует оптимальный. Этот алгоритм для всех строк даёт такие же короткие коды, как предоставляемые другими алгоритмами, с отличием на константу, зависящую от алгоритма, но не от самой строки. Соломонофф использовал этот алгоритм и предоставляемые им длины кодов для определения «универсальной вероятности» строк, на которой может быть основан индуктивный вывод последующих символов в строке. Колмогоров использовал эту теорему для определения нескольких функций строк: сложности, случайности и информации.
Когда Колмогоров узнал о работе Соломоноффа, он признал его приоритет. Несколько лет работа Соломоноффа была более известна в СССР, чем на Западе. Однако, общепринято в научном сообществе ассоциировать этот тип сложности с Колмогоровым, который говорил о случайности последовательностей, в то время как алгоритмическая вероятность стала связываться с Соломоноффым, который фокусировался на прогнозировании, используя своё открытие распределения универсальной априорной вероятности.
Существуют некоторые другие варианты колмогоровской сложности или алгоритмической информации. Один из наиболее широко используемых основан на самоограниченных программах и в основном связывается с Л. А. Левиным (1974). Аксиоматический подход к колмогоровской сложности, основанный на аксиомах Блума (1967), был введен М. Бургиным (1982).
Основные следствия В последующих рассуждениях под будем подразумевать сложность строки .
Несложно заметить, что минимальное описание строки не может быть больше, чем сама строка: приведённая выше программа GenerateFixedString, чей выход , больше на фиксированную величину.
Теорема. Существует константа , такая, что
Невычислимость колмогоровской сложности Первое следствие заключается в том, что нет эффективного способа вычисления .
Теорема. — невычислимая функция.
Другими словами, задача вычисления алгоритмической сложности произвольной строки является алгоритмически неразрешимой — не существует программы, которая бы принимала на вход и выдавала бы на выходе целое число . Покажем это с помощью противоречия путём создания программы, которая создает строку, создать которую возможно только более длинной программой. Предположим, что существует программа
function KolmogorovComplexity(string s)
которая принимает на входе и возвращает . Теперь рассмотрим программу
function GenerateComplexString(int n) for i = 1 to infinity: for each string s of length exactly i if KolmogorovComplexity(s) >= n return s quit
Эта программа вызывает подпрограмму KolmogorovComplexity. Программа пробует каждую строку, начиная с кратчайшей, пока не найдет строку со сложностью как минимум , которую возвращает. Следовательно, получив любое положительно целое число , она производит строку с колмогоровской сложностью не меньше . Эта программа имеет собственную фиксированную длину . Входом программы GenerateComplexString является целое и размер измеряется количеством битов, необходимым для его представления, которое есть . Далее рассмотрим следующую программу:
function GenerateParadoxicalString() return GenerateComplexString(n0)
Эта программа вызывает GenerateComplexString как подпрограмму и также имеет свободный параметр . Эта программа выводит строку , чья сложность составляет как минимум . При благоприятном выборе параметра мы придём к противоречию. Чтобы выбрать это значение, заметим, что описывается программой GenerateParadoxicalString, чья длина не больше, чем
где константа добавлена из-за программы GenerateParadoxicalString. Так как растёт быстрее, чем , существует значение , такое, что
Но это противоречит определению о том, что имеется сложность как минимум . То есть, по определению (), допускается, что строка , возвращаемая программой GenerateParadoxicalString, может быть создана программой длиной или больше, но GenerateParadoxicalString короче, чем . Так программа KolmogorovComplexity на самом деле не может вычислить сложность случайной строки.
Это доказательство от противного, где противоречие похоже на парадокс Берри: «Пусть — наименьшее положительно целое, которое не может быть названо меньше чем двадцатью английскими словами».В оригинале: «Let be the smallest positive integer that cannot be defined in fewer than twenty English words». Также возможно показать невычислимость путём сведения невычислимости к задаче остановки , так как и тьюринг-эквивалентны.
В сообществе программистов существует следствие, известное как теорема о полном использовании, утверждающая, что нет компилятора с совершенной оптимизацией по размеру.
Цепное правило для колмогоровской сложности
Цепное правило для колмогоровской сложности утверждает, что
Оно утверждает, что кратчайшая программа, воспроизводящая и не больше чем на превосходит по размеру программу, воспроизводящую , и программу, воспроизводящую при данном . С использованием этого выражения можно определить аналог взаимной информации для колмогоровской сложности.
Сжатие Вычислять верхнюю границу для несложно: нужно просто сжать строку каким-либо методом, реализовать соответствующий декомпрессор на выбранном языке, соединить декомпрессор со сжатой строкой и измерить длину полученной строки.
Строка сжимается на , если имеет описание, длина которого не превосходит . Это равнозначно утверждению . Если это не выполняется, то не сжимается на . Строка, не сжимаемая на 1, называется просто несжимаемой; по принципу Дирихле, несжимаемые строки должны существовать, так как есть битовых строк длиной , но только строк длиной меньше Так как существует строк длиной , то количество строк длиной — , что является конечной геометрической прогрессией с суммой равной ..
По той же причине большинство строк сложны в том смысле, что они не могут быть значительно сжаты: не намного меньше , длины в битах. Чтобы уточнить, зафиксируем значение . Существует битовых строк длиной . Равномерное распределение вероятностей на пространстве этих битовых строк определяется точно равным весовому коэффициенту для каждой строки длиной .
Теорема. Вероятность того, что строка не сжимается на равна как минимум с равномерным распределением вероятностей на пространстве битовых строк длиной .
Для доказательства этой теоремы заметим, что количество описаний длин не превосходит , полученное из геометрической прогрессии:
Остаётся как минимум
битовых строк, несжимаемых на . Для определения вероятности разделим на .
Теорема Хайтина о неполноте Нам известно, что во множестве всех возможных строк большинство строк являются сложными в том смысле, что не могут быть описаны в любом достаточно сжатом виде. Однако, оказывается, что тот факт, что конкретная строка сложна, не может быть формально доказан, если сложность строки выше определённого порога. Точная формализация представлена далее. Для начала зафиксируем частную аксиоматическую систему для натуральных чисел. Аксиоматическая система должна быть достаточно мощной, чтобы точному суждению о сложности строки можно было поставить в соответствие формулу в аксиоматической системе . Это соответствие должно обладать следующим свойством: если выводится из аксиом , то соответствующее суждение истинно.