Колмогоров сложность - Kolmogorov complexity


Из Википедии, свободной энциклопедии
Это изображение иллюстрирует часть множества Мандельброта фрактальной . Просто хранить 24-битный цвет каждого пиксела в этом изображении, потребует 1,62 миллиона байт, но небольшая компьютерная программа может воспроизвести эти 1,62 миллиона байт , используя определение множества Мандельброта и координаты углов изображения. Таким образом, Колмогоров сложность исходного файла , кодирующего это растровое изображение намного меньше , чем 1,62 миллиона байт в любой прагматической модели вычислений.

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

Понятие сложности Колмогорова может быть использовано для государства и доказать невозможность результатов сродни диагональному Кантор , теорема о неполноте Гёделя , и проблемы остановки Тьюринга . В частности, для почти всех объектов, не представляется возможным вычислить даже нижнюю границу для ее Колмогорова сложности ( Чайтину 1964 ), не говоря уже о его точное значение.

Определение

Рассмотрим следующие две строки из 32 строчных букв и цифр.

Пример 1: abababababababababababababababab
Пример 2: 4c1j5b2p0cv4w1x8rx2y39umgw5q85s7

Первая строка имеет краткое описание на английском языке, а именно « аЬ в 16 раз », который состоит из 11 символов. Второй один не имеет очевидное простое описание (используя один и тот же набор символов), кроме записывая саму строку, которая имеет 32 символов.

Более формально, сложность строки является длиной кратчайшего описания строки в некотором фиксированном универсальном языке описания (чувствительность сложности относительно выбора языка описания обсуждается ниже). Можно показать , что Колмогоров сложность любой строки не может быть больше , чем несколько байт больше , чем длина самой строки. Строки , как ABAB приведенном выше примере, чья сложность Колмогорова мала по сравнению с размером струны, не считается сложным.

Сложность Колмогорова может быть определена для любого математического объекта, но для простоты сферы применения этой статьи ограничиваются строками. Мы должны сначала определить язык описания для строк. Такой язык описания может быть основан на любом языке программирования компьютера, такие как Lisp , Pascal или Java виртуальной машины байткод. Если Р представляет собой программу , которая выводит строку х , то Р представляет собой описание х . Длина описания просто длина P в виде строки символов, умноженному на число битов в символ (например , 7 для ASCII ).

Мы могли бы, в качестве альтернативы, выбрать кодировку для машины Тьюринга , где кодирование является функцией , которая связывает каждую машину Тьюринга M битовой < M >. Если М является машина Тьюринга , которая, на входе ш , выводит строку х , то Сцепленная строка < М > ш есть описание х . Для теоретического анализа, такой подход более подходит для построения детальных формальных доказательств и , как правило , предпочтителен в научной литературе. В этой статье обсуждается неформальный подход.

Любая строка s имеет по крайней мере одно описание. Например, вторая строка выше выводится программой:

 function GenerateExample2String()
    return "4c1j5b2p0cv4w1x8rx2y39umgw5q85s7"

где первая строка выводится через (более короткий) псевдокод:

 function GenerateExample1String()
    return "ab" * 16

Если описание д ( ы ) из строки с является минимальной длиной (т.е. он использует меньшее количество бит), это называется минимальное описание в сек . Таким образом, длина д ( ы ) (то есть числа битов в описании) является Колмогоров сложность из S , написанный К ( ы ). Символично,

K ( s ) = | д ( ы ) |.

Длина кратчайшего описания , будет зависеть от выбора языка описания; но эффект изменения языков ограничено (результат называется теоремой инвариантности ). Стандартный учебник является автором Мин Ли и Паул Витани в ссылках.

теорема инвариантности

Неформальная лечение

Есть некоторые языки описания, которые являются оптимальными, в следующем смысле: учитывая любое описание объекта в языке описания, сказал описание может быть использовано в оптимальном языке описания с постоянная накладными расходами. Константа зависит только от языков, участвующих, а не на описание объекта, ни объекта описывается.

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

  • Первая часть описывает другой язык описания.
  • Вторая часть представляет собой описание объекта на этом языке.

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

Теорема инвариантности следующим образом : Для любого языка описания L , оптимальный язык описания, по крайней мере столь же эффективный , как L , с некоторыми постоянная накладными расходами.

Доказательство: Любое описание D в L может быть преобразовано в описание в оптимальном языке описания сначала L в виде компьютерной программы P (часть 1), а затем , используя оригинальное описание D в качестве входных данных для этой программы (часть 2). Общая длина этого нового описания D ' представляет собой (приблизительно):

| D ' | = | P | + | D |

Длина Р является константой , которая не зависит от D . Таким образом, существует не более постоянные накладные расходы, независимо от объекта , описываемым. Поэтому оптимальный язык универсален до этой аддитивной постоянной.

Более формальное лечение

Теорема : Если К 1 и К 2 является функция сложности относительно Тьюринга языков описания L 1 и L 2 , то существует константа C  - которая зависит только от языков L 1 и L 2 выбирает - таким образом, что

S . - сК 1 ( с ) - K 2 ( ы ) ≤ C .

Доказательство : В силу симметрии, достаточно доказать , что есть некоторые постоянные с , что для всех строк с

К 1 ( ы ) ≤ K 2 ( ы ) + гр .

Теперь предположим, что есть программа на языке L 1 , который действует в качестве переводчика для L 2 :

  function InterpretLanguage(string p)

где р представляет собой программу , в L 2 . Интерпретатор характеризуется следующим свойством:

Запуск InterpretLanguageна входе р возвращает результат выполнения р .

Таким образом, если Р представляет собой программу , в L 2 , который является минимальным описание с , то InterpretLanguage( Р ) возвращает строку с . Длина этого описания с представляет собой сумму

  1. Длина программы InterpretLanguage, которую мы можем принять как константу с .
  2. Длина Р , который , по определению, К 2 ( ы ).

Это доказывает, что желаемую верхнюю границу.

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

Алгоритмическая теория информации является область информатики, изучающая Колмогорова сложность и другие меры сложности на строках (или других структур данных ).

Понятие и теория Колмогорова Сложность основана на решающей теореме первой обнаруженной Реем Соломонов , который опубликовал его в 1960 году, описывая его в «Предварительный отчет об общей теории индуктивных умозаключений» как часть его изобретения алгоритмической вероятности . Он дал более полное описание в своих публикациях 1964 года, «формальной теории индуктивного вывода,» Часть 1 и Часть 2 в информации и управления .

Андрей Колмогоров позже независимо опубликовал эту теорему Проблемы Inform. Передача в 1965 г. Хайтин также представляет эту теорему в J. ACM  - документ Чайтину был представлен октября 1966 и пересмотрен в декабре 1968 года, и цитирует оба документа Соломонов - х и Колмогорова.

Теорема утверждает, что среди алгоритмов, которые декодируют строки из их описаний (кодов) существует оптимальный. Этот алгоритм для всех строк, позволяет коды короче, допускаемых любым другим алгоритмом до аддитивной постоянной, зависящей от алгоритмов, но не на самих строк. Соломоны использовали этот алгоритм и код длину позволяет, чтобы определить «универсальную вероятность» строки, на которой может быть основан индуктивный вывод последующих цифр строки. Колмогоров использовал эту теорему для определения несколько функций строк, включая сложность, хаотичность и информацию.

Когда Колмогоров стал известен о работе Соломонов, он признал приоритет Соломонов в. В течение нескольких лет работа Соломонов была более известна в Советском Союзе , чем в западном мире. По общему мнению , в научном сообществе, однако, в том, чтобы связать этот тип сложности с Колмогоровым, который был обеспокоен хаотичностью последовательности, в то время как Алгоритмическая Вероятность стала ассоциироваться с Соломонами, который сосредоточен на предсказании , используя его изобретение универсального априорного распределения вероятностей , Более широкая область охватывает описательную сложность и вероятность часто называют Колмогоров сложностью. Ученый Мин Ли считает , что этот пример эффекта Матфея : «... для всех , кто имеет больше будет дано ...»

Есть несколько других вариантов сложности Колмогорова или алгоритмической информации. Наиболее широко используется один основан на саморазграничен программ , и в основном из - за Леонид Левин (1974).

Аксиоматический подход к колмогоровской сложности на основе Blum аксиом (Blum , 1967) был введен Марком Burgin в документе , представленном для публикации А. Н. Колмогорова.

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

В последующем обсуждении, пусть K ( s ) является сложность строки с .

Не трудно видеть , что минимальное описание строки не может быть слишком много больше , чем сама строка - программа GenerateFixedStringвыше , которая выводит S является фиксированной суммой больше , чем с .

Теорема : Существует постоянная с такая , что

S . K ( s ) ≤ | S | + Гр .

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

Теорема : Там существуют строки сколь угодно большой сложности Колмогорова. Формально: для каждого п ∈ ℕ, есть строка сек с К ( ы ) ≥ п .

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

Теорема : K не вычислимая функция . Другими словами, нет никакой программы , которая принимает строку S в качестве входных данных и производит целое число K ( ы ) в качестве выходного сигнала.

Следующий косвенное доказательство использует простой Pascal -like языка для обозначения программ; ради простоты стойкой предположить его описание (т.е. интерпретатора ) , чтобы иметь длину 1 400 000 бит. Предположим противоречия есть программа

  function KolmogorovComplexity(string s)

который принимает в качестве входных данных строки S и возвращает K ( ы ); ради доказательства простоты предположим , длина программы будет 7 000 000 000 бит. Теперь рассмотрим следующую программу длиной 1288 бит:

  function GenerateComplexString()
     for i = 1 to infinity:
        for each string s of length exactly i
           if KolmogorovComplexity(s) >= 8000000000
              return s

Используя в KolmogorovComplexityкачестве подпрограммы, программа пытается каждая строка, начиная с самым коротким, пока он не возвращает строку с колмогоровской сложностью по крайней мере , 8 000 000 000 бит, то есть строки , которые не могут быть получены с помощью любой программы короче , чем 8 000 000 000 бит. Тем не менее, общая длина указанной выше программы , которая производится S составляет всего 7 001 401 288 битов, что приводит к противоречию. (Если код KolmogorovComplexityкороче, противоречие остается. Если она больше, константа используется в GenerateComplexStringвсегда можно изменить соответствующим образом .)

Выше доказательство использует противоречие , аналогичную на парадокс Берри : « 1 2 наименьшее 3 положительное 4 целое число 5 , что 6 не может 7 быть 8 определено 9 в 10 меньше 11 , чем 12 двадцать 13 английский 14 слов». Кроме того , можно показать , не-вычислимость К восстановлению из не-вычислимости проблемы остановки H , так как К и Н является Тюринг эквивалентно .

Существует следствие, юмористический называется « полная занятость теорема » в языке программирования сообщества, заявив , что не существует идеального размера оптимизирующего компилятора.

Наивная попытка программы для вычисления K

На первый взгляд может показаться тривиальным , чтобы написать программу , которая может вычислить K ( ы ) для любых с (таким образом опровергая выше теорему), например, следующее:

  function KolmogorovComplexity(string s)
     for i = 1 to infinity:
        for each string p of length exactly i
           if isValidProgram(p) and evaluate(p) == s
              return i

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

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

Правило цепи для сложности Колмогорова

Правило цепи для сложности Колмогорова утверждает, что

К ( Х , Y ) ≤ K ( X ) + K ( Y | X ) + O (журнал ( К ( Х , Y ))).

Он утверждает , что самую короткую программу , которая воспроизводит X и Y не является не более чем логарифмический член больше , чем программа для воспроизведения X и программ для воспроизведения Y заданного X . Используя это утверждение, можно определить аналог взаимной информации для сложности Колмогорова .

компрессия

Это просто вычислить верхние границы K ( ый ) - просто сжать строку s с каким - либо способом, осуществлять соответствующий декомпрессор на выбранном языке, конкатенацию декомпрессора к сжатой строке, и измерить длину полученной строки - конкретно, размер самораспаковывающийся архив в данном языке.

Строка s является сжимаемым на число с , если он имеет описание, длина которого не превышает | S | - гр бит. Это равносильно тому, что K ( s ) ≤ | S | - с . В противном случае, s несжимаема на с . Строка несжимаема на 1 называются просто несжимаемо  - по принципу Дирихля , который применяется , потому что каждая сжимаются строка отображает только один несжатые строки, несжимаемая строка должна существовать, так как есть 2 п битовых строк длина п , но только 2 п - 1 более короткие строки, то есть строки длиной менее п , (т.е. с длиной 0, 1, ..., п - 1).

По той же причине, большинство строк сложны в том смысле , что они не могут быть существенно сжатом - их K ( s ) не намного меньше , чем | s |, длина х в битах. Для того, чтобы сделать это точно, фиксируем значение п . Есть 2 п bitstrings длины п . Равномерная вероятность распределение на пространстве этих bitstrings назначает точно равный вес 2 - п для каждой строки длиной п .

Теорема : С равномерным распределением вероятностей на пространстве bitstrings длины п , вероятность того, что строка несжимаема по с , по крайней мере 1 - 2 - с + 1 + 2 - п .

Для доказательства теоремы заметим , что число описаний длины , не превосходящей п - гр определяется геометрической прогрессии:

1 + 2 + 2 2 + ... 2 п - с = 2 п - с + 1 - 1.

Там остаются по крайней мере,

2 п - 2 п - с + 1 + 1

bitstrings длиной п , которые несжимаемы от гр . Для того, чтобы определить вероятность, разделите на 2 п .

теорема о неполноте Чайтину в

Колмогоров сложность К ( ы ) , и два вычислимые нижней границы функции prog1(s), prog2(s). Горизонтальная ось ( логарифмическая шкала ) перечисляет все струны S , упорядоченную по длине; вертикальная ось ( линейная шкала ) измеряет сложность Колмогорова в битах . Большинство строки несжимаема, то есть их сложность Колмогорова превышает их длину на постоянную величину. 17 сжимаемые струны показано на рисунке, появляются как почти вертикальные склоны. Из теоремы о неполноте Чайтина (1974), на выходе любой программы вычисления нижней оценки сложности Колмогорова не может превышать некоторый фиксированный предел, который не зависит от входной строки s .

Мы знаем , что в множестве всех возможных строк, большинство строк сложны в том смысле , что они не могут быть описаны в любом значительно «сжатым» способом. Тем не менее, оказывается, что тот факт , что конкретная строка сложна , не может быть формально доказан, если сложность строки выше определенного порогового значения. Точной формализации заключается в следующем. Во- первых, зафиксировать определенную систему аксиомой S для натуральных чисел . Аксиоматическая система должна быть достаточно мощным , так что, чтобы некоторые утверждения А о сложности строк, можно связать формулу F A в S . Эта ассоциация должна иметь следующее свойство:

Если Р выводима из аксиом S , то соответствующее утверждение должно быть истинным. Это «формализация» может быть достигнута либо путем искусственного кодированием , такие как геделевская нумерация , либо формализация , который более четко уважает намеченную интерпретацию S .

Теорема : Там существует константа L (который только зависит от конкретной системы аксиоматического и выбора языка описания), что не существует строка s , для которых оператора

К ( ы ) ≥ L (как формализовано в S )

может быть доказано в рамках аксиоматической системы S .

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

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

Предположение (X) : Для любого целого п существует строка s , для которого существует доказательство в S формулы « К ( ы ) ≥  п » (который мы предполагаем , могут быть оформлены в S ).

Мы можем найти эффективное перечисление всех формальных доказательств в S некоторой процедурой

  function NthProof(int n)

который принимает в качестве входных данных н и выводит некоторые доказательства. Эта функция перечисляет все доказательства. Некоторые из них являются доказательства для формул мы не заботимся о здесь, так как каждое возможное доказательство на языке S производится для некоторого п . Некоторые из них являются сложность формулы вида K ( ы ) ≥  п где х и п константы в языке S . Существует программа

  function NthProofProvesComplexityFormula(int n)

который определяет , является ли п фактически доказывает й доказательство сложности формулы K ( s ) ≥  L . Строки s и целое число L , в свою очередь, вычислимы программ:

  function StringNthProof(int n)
  function ComplexityLowerBoundNthProof(int n)

Рассмотрим следующую программу

  function GenerateProvablyComplexString(int n)
     for i = 1 to infinity:
        if  NthProofProvesComplexityFormula(i) and ComplexityLowerBoundNthProof(i) ≥ n
           return StringNthProof(i)

Учитывая п , эта программа пытается каждое доказательство до тех пор, пока не найдет строку и доказательства в формальной системе S формулы K ( s ) ≥  L для некоторого L  ≥  п . Программа завершается наш Успенская (X) . Теперь эта программа имеет длину U . Существует целое число п 0 такое , что U  + войти 2 ( п 0 ) +  С  <  п 0 , где С представляет собой накладные расходы

   function GenerateProvablyParadoxicalString()
      return GenerateProvablyComplexString(n0)

(заметим , что п 0 жестко закодирован в указанную выше функцию, и журнал слагаемое 2 ( п 0 ) уже позволяет его кодирования). Программа GenerateProvablyParadoxicalString выводит строку s , для которого существует L такой , что К ( ы ) ≥  L может быть формально доказан в S с L  ≥  п 0 . В частности, К ( ы ) ≥  п 0 верно. Тем не менее, с также описан программой длины U  + войти 2 ( п 0 ) +  С , поэтому его сложность меньше п 0 . Это противоречие доказывает , Успенская (X) не может иметь места .

Подобные идеи используются для доказательства свойств константы хайтина .

Минимальная длина сообщения

Минимальный принцип длины сообщения статистического и индуктивного вывод и машинное обучение был разработан CS Уоллесом и DM Бултон в 1968. MML является байесовским (т.е. он включает в себя предыдущие убеждения) и теоретико-информационный. Он имеет желаемые свойства статистической инвариантности (т.е. логического вывода переходит с повторной параметризации, например, от полярных координат к декартовым координатам), статистической последовательности (то есть даже при очень жестких проблем, MML будет сходиться к любой базовой модели) и эффективность ( т.е. модель MML будет сходиться к любой истинной базовой модели примерно так же быстро , как это возможно). CS Уоллес и DL Dowe (1999) показали формальную связь между MML и алгоритмической теории информации (или сложности Колмогорова).

Колмогоров хаотичность

Колмогоров случайность определяет строку (обычно из битов ) как являющийся случайным тогда и только тогда , когда он короче , чем любая компьютерная программа , которая может производить эту строку. Чтобы сделать это точным, универсальный компьютер должен быть указан (или универсальная машина Тьюринга), так что «программа» означает программу для этой универсальной машины. Случайная строка в этом смысле «несжимаемая» в том , что невозможно «сжать» строку в программу, длина которой меньше , чем длина самой строки. Подсчета аргумент используется , чтобы показать , что для любого универсального компьютера, существует по крайней мере один алгоритмический случайная последовательность каждой длины. Если какая - либо конкретная строка является случайной, однако, зависит от конкретного универсального компьютера , который выбран.

Это определение может быть расширено , чтобы определить понятие случайности для бесконечных последовательностей из конечного алфавита. Эти алгоритмически случайные последовательности могут быть определены в трех эквивалентных способов. Один из способов используют эффективный аналог теории меры ; другой использует эффективные мартингалы . Третий способ определяет бесконечная последовательность , чтобы быть случайной , если префикс свободного Колмогоров сложность ее начальных отрезков растет достаточно быстро - должна быть постоянным с таким образом, что сложность начального отрезка длиной п всегда по крайней мере п - с . Это определение, в отличии от определения случайности для конечной струны, не зависят от которой универсальной машины используются для определения префикса свободного Колмогорова сложности.

Отношение к энтропии

Для динамических систем, энтропии и скорости алгоритмической сложности траекторий связаны по теореме Брудна, что равенство К (х, Т) = Н (Т) имеет место для почти всех х.

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

Условные версии

Условная сложность Колмогорова двух строк , грубо говоря, определяется как сложность Колмогорова х заданных у в качестве вспомогательного входа к процедуре.

Существует также длину условной сложности , которая является сложностью й с учетом длиной х , как известно / ввод.

Смотрите также

Заметки

Рекомендации

дальнейшее чтение

  • Блюм, М. (1967). «По размеру машин». Информация и управление . 11 (3): 257. DOI : 10.1016 / S0019-9958 (67) 90546-3 .
  • Брудно, А. Энтропия и сложность траекторий динамической системы, Труды Московского математического общества, 2: 127. {151, 1983.
  • Обложка, Томас М. и Томас, Джой А., Элементы теории информации , 1 - е издание. Нью - Йорк: Wiley-Interscience, 1991. ISBN  0-471-06259-6 . 2 - е издание. Нью - Йорк: Wiley-Interscience, 2006. ISBN  0-471-24195-4 .
  • Лайош, Rónyai и Габор, Ivanyos и Réka, Сабо, Algoritmusok . TypoTeX, 1999. ISBN  963-279-014-6
  • Ли Мин; Vitányi, Paul (1997). Введение Колмогорова Сложность и ее применения . Springer. ISBN  978-0387339986 .
  • Ю. Манин, Курс математической логики , Springer-Verlag, 1977. ISBN  978-0-7204-2844-5
  • Sipser, Майкл, Введение в теорию вычислений , PWS Publishing Company, 1997. ISBN  0-534-95097-3 .

внешняя ссылка