Колмогоровская сложность

Это изображение иллюстрирует часть множества Мандельброта фрактала . Для простого хранения 24-битного цвета каждого пикселя этого изображения потребуется 23 миллиона байт, но небольшая компьютерная программа может воспроизвести эти 23 МБ, используя определение множества Мандельброта и угловые координаты изображения. Таким образом, колмогоровская сложность этого образа намного меньше 23 МБ в любой прагматической модели вычислений . PNG уменьшает его только до 1,6 МБ, что меньше, чем необработанные данные, но намного превышает колмогоровскую сложность. Универсальное сжатие изображений

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

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

Определение

Интуиция

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

abababababababababababababababab , и

4c1j5b2p0cv4w1x8rx2y39umgw5q85s7

Первая строка имеет краткое англоязычное описание, а именно «write ab 16 раз», которое состоит из 17 символов. Второй не имеет очевидного простого описания (с использованием того же набора символов), кроме записи самой строки, например, «write 4c1j5b2p0cv4w1x8rx2y39umgw5q85s7», которая имеет 38 символов. Следовательно, можно сказать, что операция записи первой строки имеет «меньшую сложность», чем запись второй.

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

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

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

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

function GenerateString2()
    return "4c1j5b2p0cv4w1x8rx2y39umgw5q85s7"

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

function GenerateString1()
    return "ab" × 16

Если описание d ( s ) строки s имеет минимальную длину (т.е. использует наименьшее количество битов), оно называется минимальным описанием s минимальном , а длина d ( s ) (т.е. количество битов в описание) — это колмогоровская сложность s ( , записанная K ) s . Символически,

К ( s ) знак равно | д ( с )|.

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

Обычная колмогоровская сложность C

Существует два определения колмогоровской сложности: простое и беспрефиксное . Простая сложность — это минимальная длина описания любой программы и обозначается $C(x)$ а беспрефиксная сложность — это минимальная длина описания любой программы, закодированной в беспрефиксном коде, и обозначается $K(x)$. Простая сложность более интуитивна, но сложность без префиксов легче изучать.

По умолчанию все уравнения справедливы только до аддитивной константы. Например, $f(x)=g(x)$ действительно означает, что $f(x)=g(x)+O(1)$, то есть, $\exists c,\forall x,|f(x)-g(x)|\leq c$.

Позволять $U:2^{*}\to 2^{*}$ быть вычислимой функцией, отображающей конечные двоичные строки в двоичные строки. Это универсальная функция тогда и только тогда, когда для любого вычислимого $f:2^{*}\to 2^{*}$, мы можем закодировать функцию в «программе» $s_{f}$, такой, что $\forall x\in 2^{*},U(s_{f}x)=f(x)$. Мы можем подумать о $U$ в качестве интерпретатора программы, который принимает начальный сегмент, описывающий программу, за которым следуют данные, которые программа должна обработать.

Одна из проблем с простой сложностью заключается в том, что $C(xy)\not <C(x)+C(y)$, потому что, интуитивно говоря, не существует общего способа определить, где разделить выходную строку, просто взглянув на объединенную строку. Мы можем разделить его, указав длину $x$ или $y$, но это займет $O(\min(\ln x,\ln y))$ дополнительные символы. Действительно, для любого $c>0$ существует $x,y$ такой, что $C(xy)\geq C(x)+C(y)+c$.

Обычно неравенства простой сложности имеют такой термин, как $O(\min(\ln x,\ln y))$ с одной стороны, тогда как те же неравенства с беспрефиксной сложностью имеют только $O(1)$.

Основная проблема простой сложности заключается в том, что в программу запрятано что-то дополнительное. Программа не только представляет что-то своим кодом, но и представляет свою собственную длину. В частности, программа $x$ может представлять двоичное число до $\log _{2}|x|$, просто по своей длине. Другими словами, это похоже на то, как если бы мы использовали символ завершения для обозначения места окончания слова, и поэтому мы используем не 2 символа, а 3. Чтобы исправить этот недостаток, мы вводим беспрефиксную колмогоровскую сложность.

Беспрефиксная колмогоровская сложность K

Код без префиксов является подмножеством $2^{*}$ такое, что учитывая любые два разных слова $x,y$ в наборе ни один из них не является префиксом другого. Преимущество кода без префиксов состоит в том, что мы можем построить машину, которая считывает слова из кода вперед в одном направлении, и как только она считывает последний символ слова, она знает , что слово закончено, и не делает этого. необходимость возврата или символ завершения.

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

Это дает нам следующий формальный способ описания K .

• Исправьте универсальную машину Тьюринга без префиксов с тремя лентами: лентой чтения, бесконечной в одном направлении, рабочей лентой, бесконечной в двух направлениях, и лентой записи, бесконечной в одном направлении.
• Машина может читать с ленты чтения только в одном направлении (без обратного отслеживания) и записывать на ленту записи только в одном направлении. Он может читать и записывать рабочую ленту в обоих направлениях.
• Рабочая лента и лента записи начинаются с нулей. Считывание ленты начинается с входного префиксного кода, за которым следуют все нули.
• Позволять $S$ быть кодом без префиксов на $2^{*}$, используемый универсальной машиной Тьюринга.

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

Сложность строки без префикса $x$ это кратчайший префиксный код, который делает вывод машины $x$: $$K(x):=\min\{|c|:c\in S,U(c)=x\}$$

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

Неформальное обращение

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

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

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

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

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

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

| Д' | = | П | + | Д |

Длина P не зависящая от D. — константа , Таким образом, накладные расходы не превышают постоянные, независимо от описываемого объекта. Следовательно, оптимальный язык универсален с точностью до этой аддитивной константы.

Более формальный подход

Теорема : Если K ₁ и K ₂ являются функциями сложности относительно языков полного описания Тьюринга L ₁ и L ₂ , то существует константа c – которая зависит только от выбранных языков L ₁ и L ₂ – такая, что

∀ с . - c ≤ K ₁ ( s ) - K ₂ ( s ) ≤ c .

Доказательство . В силу симметрии достаточно доказать, что существует некоторая константа c такая, что для всех строк s

K ₁ ( s ) ≤ K ₂ ( s ) + c .

Теперь предположим, что существует программа на языке которая _{действует} как интерпретатор L2 L1 _, :

function InterpretLanguage(string p)

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

Бег InterpretLanguage на входе p возвращает результат запуска p .

Таким образом, если P — программа в L2 _, являющаяся минимальным описанием s , то InterpretLanguage( P ) возвращает строку s . Длина этого описания s равна сумме

1. Продолжительность программы InterpretLanguage, которую мы можем принять за константу c .
2. Длина P , которая по определению равна K ₂ ( s ).

Это доказывает требуемую верхнюю оценку.

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

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

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

Позднее Андрей Колмогоров независимо опубликовал эту теорему в журнале «Проблемы Информ». Передача инфекции в 1965 году. Грегори Чайтин также представляет эту теорему в J. ACM - статья Чайтина была представлена ​​в октябре 1966 года и исправлена ​​в декабре 1968 года, и цитирует статьи Соломонова и Колмогорова.

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

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

Существует несколько других вариантов колмогоровской сложности или алгоритмической информации. Наиболее широко используемый из них основан на саморазграничивающих программах и принадлежит главным образом Леониду Левину (1974).

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

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

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

Неравенства

Мы опускаем аддитивные факторы $O(1)$. Этот раздел основан на.

Теорема. $C(x)\leq K(x)+2\log _{2}C(x)$

Доказательство. Возьмите любую программу для универсальной машины Тьюринга, используемой для определения простой сложности, и преобразуйте ее в программу без префиксов, сначала закодировав длину программы в двоичном формате, а затем преобразуя длину в кодирование без префиксов. Например, предположим, что длина программы равна 9, тогда мы можем преобразовать ее следующим образом: $$9\mapsto 1001\mapsto 11-00-00-11-\color {red}{01}$$где мы удваиваем каждую цифру, а затем добавляем код завершения. Универсальная машина Тьюринга без префиксов может затем читать любую программу для другой машины следующим образом: $$[{\text{code for simulating the other machine}}][{\text{coded length of the program}}][{\text{the program}}]$$Первая часть программирует машину для имитации другой машины и представляет собой постоянные накладные расходы. $O(1)$. Вторая часть имеет длину $\leq 2\log _{2}C(x)+3$. Третья часть имеет длину $C(x)$.

Теорема : существует $c$ такой, что $\forall x,C(x)\leq |x|+c$. Более кратко, $C(x)\leq |x|$. Сходным образом, $K(x)\leq |x|+2\log _{2}|x|$, и $K(x||x|)\leq |x|$.

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

Теорема. (дополнительные информационные границы, субаддитивность)

• $K(x|y)\leq K(x)\leq K(x,y)\leq \max(K(x|y)+K(y),K(y|x)+K(x))\leq K(x)+K(y)$

• $K(xy)\leq K(x,y)$

Обратите внимание, что нет возможности сравнивать $K(xy)$ и $K(x|y)$ или $K(x)$ или $K(y|x)$ или $K(y)$. Существуют строки такие, что вся строка $xy$ легко описать, но его подстроки описать очень сложно.

Теорема. (симметрия информации) $K(x,y)=K(x|y,K(y))+K(y)=K(y,x)$.

Доказательство. Одна сторона простая. Для другой стороны с $K(x,y)\geq K(x|y,K(y))+K(y)$, нам нужно использовать счетный аргумент (стр. 38 ).

Теорема. (неувеличение информации) Для любой вычислимой функции $f$, у нас есть $K(f(x))\leq K(x)+K(f)$.

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

Невычислимость колмогоровской сложности.

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

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

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

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

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

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

Формальное доказательство невычислимости K

Теорема : существуют строки сколь угодно большой колмогоровской сложности. Формально: для каждого натурального числа n существует строка s такая, что K ( s ) ≥ n .

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

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

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

function KolmogorovComplexity(string s)

который принимает на вход строку s и возвращает K ( s ). Все программы имеют конечную длину, поэтому для простоты доказательства примем ее равной 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 всегда можно изменить соответствующим образом.)

Приведенное выше доказательство использует противоречие, подобное противоречию парадокса Берри : « ₁ ​ ₂ самых маленьких ₃ положительных ₄ целое число ₅ это ₆ не могу ₇ быть ₈ определено ₉ дюймов _{на 10} меньше ₁₁ чем ₁₂ двадцать ₁₃ английский ₁₄ слов». Также можно показать невычислимость K путем сведения к невычислимости проблемы остановки H , поскольку K и H тьюринг -эквивалентны .

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

Цепное правило для колмогоровской сложности.

Основная статья: Цепное правило для колмогоровской сложности

Правило цепочки Колмогоровская сложность утверждает, что существует константа c такая, что для всех X и Y :

K ( X , Y = K ( X ) K ( Y X + ) (X,Y|

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

Сжатие

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

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

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

Теорема : При равномерном распределении вероятностей в пространстве битовых строк длины n вероятность того, что строка несжимаема с помощью c, равна как минимум 1 - 2. ^{− с +1} + 2 ^{− п} .

Для доказательства теоремы заметим, что количество описаний длины, не превышающей n − c, задается геометрической прогрессией:

1 + 2 + 2 ² + ... + 2 ^{п - с} = 2 ^{п - с +1} − 1.

Осталось по крайней мере

2 ^н − 2 ^{п - с +1} + 1

битовые строки длины n , несжимаемые с помощью c . Чтобы определить вероятность, разделите на 2 ^н .

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

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

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

Если F _A доказуемо из аксиом S , то соответствующее утверждение A должно быть истинным. Эта «формализация» может быть достигнута на основе нумерации Гёделя .

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

K ( s ) ≥ L (формализовано в S )

может быть доказано в пределах S .

Идея доказательства : Доказательство этого результата смоделировано на самореферентной конструкции, используемой в парадоксе Берри . Сначала мы получаем программу, которая перечисляет доказательства внутри S , и задаем процедуру P которая принимает в качестве входных данных целое число L и печатает строки x , находящиеся в пределах доказательств внутри S утверждения K ( x ) ≥ L. , Установив затем L больше, чем длина этой процедуры P , мы получим, что требуемая длина программы для печати x , как указано в K ( x ) ≥ L, как минимум L, тогда будет меньше суммы L, поскольку строка x напечатан с помощью процедуры P. был Это противоречие. не может Таким образом, система доказательств S доказать K ( x ) ≥ L для L сколь угодно большого размера, в частности, для L большей, чем длина процедуры P (которая конечна).

Доказательство :

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

function NthProof(int n)

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

function NthProofProvesComplexityFormula(int n)

который определяет, действительно ли - е доказательство доказывает формулу сложности K ( s ) ≥ L. n Строки 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)

Учитывая n , эта процедура пробует каждое доказательство, пока не найдет строку и доказательство в формальной системе S формулы K ( s ) ≥ L для некоторого L ≥ n ; если такого доказательства не существует, оно зацикливается навсегда.

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

GenerateProvablyComplexString(n0)

где константа n ₀ будет определена позже. Общая длина программы может быть выражена как U +log ₂ ( n ₀ ), где U — некоторая константа, а log ₂ ( n ₀ ) представляет длину целочисленного значения n ₀ при разумном предположении, что оно закодировано двоичными цифрами. . Мы выберем n ₀ больше длины программы, то есть такое, что n ₀ > U +log ₂ ( n ₀ ). Это, очевидно, верно для достаточно большого n ₀ , поскольку левая часть растет линейно по n ₀ , тогда как правая часть растет логарифмически по n ₀ вплоть до фиксированной константы U .

доказательство вида « K ( s )≥ L » с L ≥ n0 _{, в} невозможно получить Тогда в S чем можно убедиться косвенным рассуждением : Если ComplexityLowerBoundNthProof(i) может вернуть значение ≥ n ₀ , тогда цикл внутри GenerateProvablyComplexString в конечном итоге завершится, и эта процедура вернет строку s такую, что

	К ( с )
≥	п 0		путем строительства GenerateProvablyComplexString
>	U + журнал 2 ( п 0 )		по выбору n 0
≥	К ( с )		поскольку s было описано программой с такой длиной

Это противоречие, КЭД

Как следствие, приведенная выше программа с выбранным значением n ₀ должна работать вечно.

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

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

Основная статья: Минимальная длина сообщения

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

Колмогоровская случайность

См. Также: Алгоритмически случайная последовательность.

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

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

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

Для динамических систем скорость энтропии и алгоритмическая сложность траекторий связаны теоремой Брудно, согласно которой равенство $K(x;T)=h(T)$ подходит почти для всех $x$.

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

Теорема. (Теорема 14.2.5 ) Условная колмогоровская сложность двоичной строки $x_{1:n}$ удовлетворяет $${\frac {1}{n}}K(x_{1:n}|n)\leq H_{b}\left({\frac {1}{n}}\sum _{i}x_{i}\right)+{\frac {\log n}{2n}}+O(1/n)$$где $H_{b}$ — двоичная функция энтропии (не путать со скоростью энтропии).

Проблема с остановкой

Функция сложности Колмогорова эквивалентна решению проблемы остановки.

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

Другое направление гораздо сложнее. Он показывает, что по колмогоровской функции сложности можно построить функцию $p$, такой, что $p(n)\geq BB(n)$ для всех больших $n$, где $BB$ — функция сдвига Busy Beaver (также обозначаемая как $S(n)$). Изменяя функцию при более низких значениях $n$ мы получаем верхнюю границу $BB$, что решает проблему остановки.

Рассмотрите эту программу ${\textstyle p_{K}}$, который принимает входные данные как ${\textstyle n}$и использует ${\textstyle K}$.

• Перечислить все строки длины ${\textstyle \leq 2n+1}$.

• Для каждой такой строки ${\textstyle x}$, перечислить все (без префиксов) программы длины $K(x)$ пока один из них не выведет ${\textstyle x}$. Запишите время его выполнения ${\textstyle n_{x}}$.
• Выведите самый большой ${\textstyle n_{x}}$.

Докажем от противного, что ${\textstyle p_{K}(n)\geq BB(n)}$ для всех больших ${\textstyle n}$.

Позволять ${\textstyle p_{n}}$ быть длинным и занятым бобром $n$. Рассмотрим эту программу (без префиксов), которая не принимает никаких входных данных:

• Запустите программу ${\textstyle p_{n}}$и запишите продолжительность его выполнения ${\textstyle BB(n)}$.

• Генерировать все программы длиной ${\textstyle \leq 2n}$. Запустите каждый из них на срок до ${\textstyle BB(n)}$ шаги. Обратите внимание на результаты тех, которые остановились.

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

Пусть строка, выдаваемая программой, будет ${\textstyle x}$.

Программа имеет длину ${\textstyle \leq n+2\log _{2}n+O(1)}$, где $n$ происходит от длины Занятого бобра ${\textstyle p_{n}}$, $2\log _{2}n$ (без префиксов) получается в результате использования дельта-кода Элиаса для номера $n$, и $O(1)$ исходит из остальной части программы. Поэтому, $$K(x)\leq n+2\log _{2}n+O(1)\leq 2n$$для всех больших ${\textstyle n}$. Далее, поскольку возможных программ длины ${\textstyle \leq 2n}$, у нас есть ${\textstyle l(x)\leq 2n+1}$ по ячейковому принципу . По предположению, ${\textstyle p_{K}(n)<BB(n)}$, поэтому каждая строка длины ${\textstyle \leq 2n+1}$ имеет минимальную программу со временем выполнения ${\textstyle <BB(n)}$. Таким образом, строка ${\textstyle x}$ имеет минимальную программу со временем выполнения ${\textstyle <BB(n)}$. Кроме того, эта программа имеет длину ${\textstyle K(x)\leq 2n}$. Это противоречит тому, как ${\textstyle x}$ был построен.

Универсальная вероятность

Починить универсальную машину Тьюринга $U$, тот же самый, который использовался для определения (беспрефиксной) колмогоровской сложности. Определите (без префикса) универсальную вероятность строки $x$ быть $$P(x)=\sum _{U(p)=x}2^{-l(p)}$$Другими словами, это вероятность того, что при наличии на входе равномерно случайного двоичного потока универсальная машина Тьюринга остановится после чтения определенного префикса потока и выведет $x$.

Примечание. $U(p)=x$ не означает, что входной поток $p000\cdots$, но что универсальная машина Тьюринга в какой-то момент остановится после прочтения начального сегмента $p$, не читая никаких дальнейших входных данных, и что, когда он останавливается, он записывает $x$ на выходную ленту.

Теорема. (Теорема 14.11.1 ) $\log {\frac {1}{P(x)}}=K(x)+O(1)$

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

Условная колмогоровская сложность двух строк. $K(x|y)$ грубо говоря, определяется как колмогоровская сложность x при условии, что y является вспомогательным входом в процедуру.

Существует также сложность, обусловленная длиной $K(x|L(x))$, что представляет собой сложность x длины x . с учетом известной/входной

См. также

• Парадокс Берри
• Код гольфа
• Сжатие данных
• Описательная теория сложности
• Грамматическая индукция
• Индуктивное рассуждение
• Структурная функция Колмогорова
• Расстояние Левенштейна
• Теория индуктивного вывода Соломонова
• Выборочная энтропия

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

• Блюм, М. (1967). «О размерах машин» . Информация и контроль . 11 (3): 257. doi : 10.1016/S0019-9958(67)90546-3 .
• Брудно, А. (1983). «Энтропия и сложность траекторий динамической системы». Труды Московского математического общества . 2 : 127–151.
• Обложка, Томас М.; Томас, Джой А. (2006). Элементы теории информации (2-е изд.). Уайли-Интерсайенс. ISBN  0-471-24195-4 .
• Лайош, Роньяи; Габор, Иваньос; Река, Сабо (1999). Алгоритмы . ТайпоТекс. ISBN  963-279-014-6 .
• Ли, Мин; Витаньи, Пол (1997). Введение в колмогоровскую сложность и ее приложения . Спрингер. ISBN  978-0387339986 .
• Ю, Манин (1977). Курс математической логики . Спрингер-Верлаг. ISBN  978-0-7204-2844-5 .
• Сипсер, Майкл (1997). Введение в теорию вычислений . ПВС. ISBN  0-534-95097-3 .
• Дауни, Родни Г.; Хиршфельдт, Денис Р. (2010). «Алгоритмическая случайность и сложность» . Теория и приложения вычислимости . дои : 10.1007/978-0-387-68441-3 . ISBN  978-0-387-95567-4 . ISSN   2190-619X .

Внешние ссылки

• The Legacy of Andrei Nikolaevich Kolmogorov
• Интернет-публикации Чайтина
• Страница IDSIA Соломонова
• Обобщения алгоритмической информации Й. Шмидхубера
• «Обзор Ли Витаньи 1997» .
• Тромп, Джон. «Лямбда-исчисление Джона и игровая площадка комбинаторной логики» . Компьютерная модель лямбда-исчисления Тромпа предлагает конкретное определение K()]
• Универсальный ИИ на основе колмогоровской сложности ISBN   3-540-22139-5 Хаттера М. : ISBN   3-540-22139-5
• Дэвида Доу и Минимальная длина сообщения (MML) страницы -бритвы Оккама .
• Грюнвальд, П.; Питт, Массачусетс (2005). Мьюнг, Эй Джей (ред.). Достижения в минимальной длине описания: теория и приложения . МТИ Пресс. ISBN  0-262-07262-9 .