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

Мера алгоритмической сложности

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

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

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

Определение

Интуиция

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

abababababababababababababababab, и

4c1j5b2p0cv4w1x8rx2y39umgw5q85s7

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

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

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

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

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

функция GenerateString2() возвращает "4c1j5b2p0cv4w1x8rx2y39umgw5q85s7"

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

функция GenerateString1() возвращает "ab" × 16

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

К ( с ) = | д ( с )|.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сложность строки без префикса — это самый короткий префиксный код, который выводит машина : ${\displaystyle x}$ ${\displaystyle x}$ $${\displaystyle 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 ₂ – такая, что

∀ s . − c ≤ K ₁ ( s ) − K ₂ ( s ) ≤ c .

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

К ₁ ( с ) ≤ К ₂ ( с ) + с .

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

функция InterpretLanguage( строка  p )

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

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

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

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

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

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

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

Концепция и теория сложности Колмогорова основана на важнейшей теореме, впервые открытой Рэем Соломоновым , который опубликовал ее в 1960 году, описав ее в "Предварительном отчете об общей теории индуктивного вывода" ^[7] как часть своего изобретения алгоритмической вероятности . Он дал более полное описание в своих публикациях 1964 года "Формальная теория индуктивного вывода", часть 1 и часть 2 в Information and Control . ^{[8] [9]}

Андрей Колмогоров позже независимо опубликовал эту теорему в Problems Inform. Transmission ^[10] в 1965 году. Грегори Чайтин также представляет эту теорему в J. ACM  – статья Чайтина была представлена ​​в октябре 1966 года и пересмотрена в декабре 1968 года, и цитирует как статьи Соломонова, так и Колмогорова. ^[11]

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

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

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

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

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

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

Неравенства

Мы опускаем аддитивные факторы . Этот раздел основан на. ^[6] ${\displaystyle O(1)}$

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

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

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

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

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

• ${\displaystyle 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)}$

• ${\displaystyle K(xy)\leq K(x,y)}$

Обратите внимание, что нет способа сравнить and или or или . Существуют строки, которые легко описать целиком , но очень сложно описать ее подстроки. ${\displaystyle K(xy)}$ ${\displaystyle K(x|y)}$ ${\displaystyle K(x)}$ ${\displaystyle K(y|x)}$ ${\displaystyle K(y)}$ ${\displaystyle xy}$

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

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

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

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

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

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

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

функция KolmogorovComplexity( string s) для i = 1 до бесконечности: для каждой строки p длины ровно i, если isValidProgram(p) и estimate(p) == s возвращает i

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

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

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

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

Теорема : Существуют строки произвольно большой сложности Колмогорова. Формально: для каждого натурального числа n существует строка s с K ( s ) ≥ n . ^{[примечание 1]}

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

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

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

функция KolmogorovComplexity( строка s)

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

функция GenerateComplexString() для i = 1 до бесконечности: для каждой строки s длины ровно i, если KolmogorovComplexity(s) ≥ 8000000000 возвращает s

Используя KolmogorovComplexityв качестве подпрограммы, программа пробует каждую строку, начиная с самой короткой, пока не вернет строку с колмогоровской сложностью не менее8 000 000 000 бит, ^{[примечание 3]} т.е. строка, которая не может быть создана никакой программой короче, чем8 000 000 000 бит. Однако общая длина приведенной выше программы, которая выдала s, составляет всего7 001 401 288 бит, ^{[примечание 4]} что является противоречием. (Если код KolmogorovComplexityкороче, противоречие остается. Если он длиннее, константу, используемую в, GenerateComplexStringвсегда можно изменить соответствующим образом.) ^{[примечание 5]}

Приведенное выше доказательство использует противоречие, похожее на противоречие _{парадокса} Берри : " 1 Наименьшее ₂ положительное ₃ целое _число 4 _{такое 5} , что ₆ не может быть ₇ определено ₉ за ₁₀ меньше ₁₁ чем ₁₂ двадцать ₁₃ английских ₁₄ слов". Также возможно показать невычислимость K с помощью редукции из невычислимости проблемы остановки H , поскольку K и H эквивалентны по Тьюрингу . ^[16]

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

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

Цепное правило ^[17] для сложности Колмогорова гласит, что существует константа c такая, что для всех X и Y :

K ( X , Y ) = K ( X ) + K ( Y | X ) + c*max(1,log( K ( X , Y )))).

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

Сжатие

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

Строка s сжимаема числом c, если ее описание не превышает | s | − c бит. Это эквивалентно утверждению, что K ( s ) ≤ | s | − c . В противном случае s несжимаема числом c . Строка, несжимаемая числом 1, называется просто несжимаемой  — по принципу ящика , который применяется, поскольку каждая сжатая строка отображается только на одну несжатую строку, несжимаемые строки должны существовать, поскольку существует 2 ⁿ битовых строк длины n , но только 2 ⁿ − 1 более коротких строк, то есть строк длиной меньше n , (т. е. длиной 0, 1, ..., n − 1). ^{[примечание 6]}

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

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

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

1 + 2 + 2 ² + ... + 2 ^{n − c} = 2 ^{n − c +1} − 1.

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

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

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

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

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

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

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

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

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

может быть доказано в S. ^[18] [ ^19]

Идея доказательства : Доказательство этого результата смоделировано на основе самореферентной конструкции, используемой в парадоксе Берри . Сначала мы получаем программу, которая перечисляет доказательства в пределах 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 с помощью некоторой процедуры

функция NthProof( int  n )

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

функция NthProofProvesComplexityFormula( int  n )

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

функция StringNthProof( int  n )

функция ComplexityLowerBoundNthProof( int  n )

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

функция GenerateProvablyComplexString( int  n ) для i от 1 до бесконечности: если NthProofProvesComplexityFormula(i) и ComplexityLowerBoundNthProof(i) ≥ n  возвращает StringNthProof( i )

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

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

СгенерироватьДоказуемоСложнуюСтроку( n 0 )

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

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

Это противоречие, QED.

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

Аналогичные идеи используются для доказательства свойств постоянной Хайтина .

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

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

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

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

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

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

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

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

Теорема. (Теорема 14.2.5 ^[25] ) Условная сложность Колмогорова двоичной строки удовлетворяет условию , где — функция двоичной энтропии (не путать со скоростью энтропии). ${\displaystyle x_{1:n}}$ $${\displaystyle {\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)}$$ ${\displaystyle H_{b}}$

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

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

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

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

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

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

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

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

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

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

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

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

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

Программа имеет длину , где происходит от длины Busy Beaver , происходит от использования (без префикса) дельта-кода Элиаса для числа , и происходит от остальной части программы. Следовательно, для всех больших . Далее, поскольку существует только определенное количество возможных программ с длиной , мы имеем по принципу ящика . По предположению, , поэтому каждая строка длины имеет минимальную программу со временем выполнения . Таким образом, строка имеет минимальную программу со временем выполнения . Далее, эта программа имеет длину . Это противоречит тому, как было построено. ${\textstyle \leq n+2\log _{2}n+O(1)}$ ${\displaystyle n}$ ${\textstyle p_{n}}$ ${\displaystyle 2\log _{2}n}$ ${\displaystyle n}$ ${\displaystyle O(1)}$ $${\displaystyle 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}$

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

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

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

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

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

Условная сложность Колмогорова двух строк , грубо говоря, определяется как сложность Колмогорова x при условии, что y является вспомогательным входом процедуры. ^{[28] [29]} ${\displaystyle K(x|y)}$

Существует также сложность , зависящая от длины, которая является сложностью x при известной/входной длине x . ^{[30] [31]} ${\displaystyle K(x|L(x))}$

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

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

Примечания

1. Однако s с K ( s ) = n не обязательно существует для каждого n . Например, если n не кратно 7, никакая программа ASCII не может иметь длину ровно n бит.
2. Существует 1 + 2 + 2 ² + 2 ³ + ... + 2 ⁿ = 2 ^{n +1} − 1 различных текстов программ длиной до n бит; ср. геометрическая прогрессия . Если длины программ должны быть кратны 7 битам, существует еще меньше текстов программ.
3. Согласно предыдущей теореме такая строка существует, поэтому forцикл в конечном итоге завершится.
4. включая интерпретатор языка и код подпрограммы дляKolmogorovComplexity
5. Если KolmogorovComplexityдлина n бит, то константу m, используемую в, GenerateComplexStringнеобходимо адаптировать для удовлетворения n +1 400 000 +1218 + 7·log ₁₀ ( m ) < m , что всегда возможно, поскольку m растет быстрее, чем log ₁₀ ( m ).
6. Поскольку имеется N _L = 2 ^L строк длины L , количество строк длины L = 0, 1, ..., n − 1 равно N ₀ + N ₁ + ... + N _{n −1} = 2 ⁰ + 2 ¹ + ... + 2 ^{n −1} , что является конечной геометрической прогрессией с суммой 2 ⁰ + 2 ¹ + ... + 2 ^{n −1} = 2 ⁰ × (1 − 2 ⁿ ) / (1 − 2) = 2 ⁿ − 1

Ссылки

1. Колмогоров, Андрей (декабрь 1963 г.). «О таблицах случайных чисел». Sankhyā: The Indian Journal of Statistics, Series A (1961-2002) . 25 (4): 369–375. ISSN  0581-572X. JSTOR  25049284. MR  0178484.
2. Колмогоров, Андрей (1998). «О таблицах случайных чисел». Теоретическая информатика . 207 (2): 387–395. doi : 10.1016/S0304-3975(98)00075-9 . MR  1643414.
3. Витаний, Пол МБ (апрель 2020 г.). «Насколько невычислима сложность Колмогорова?». Энтропия . 22 (4): 408. arXiv : 2002.07674 . Bibcode : 2020Entrp..22..408V. doi : 10.3390/e22040408 . ISSN  1099-4300. PMC 7516884. PMID  33286182 . 
4. (Дауни и Хиршфельдт, 2010), Теорема 3.1.4
5. (Дауни и Хиршфельдт, 2010), Раздел 3.5
6. Hutter, Marcus (2007-03-06). "Алгоритмическая теория информации". Scholarpedia . 2 (3): 2519. Bibcode :2007SchpJ...2.2519H. doi : 10.4249/scholarpedia.2519 . hdl : 1885/15015 . ISSN  1941-6016.
7. Соломонофф, Рэй (4 февраля 1960 г.). Предварительный отчет об общей теории индуктивного вывода (PDF) . Отчет V-131 (Отчет). Пересмотр опубликован в ноябре 1960 г. Архивировано (PDF) из оригинала 2022-10-09.
8. Соломонофф, Рэй (март 1964). "Формальная теория индуктивного вывода. Часть I" (PDF) . Информация и управление . 7 (1): 1–22. doi : 10.1016/S0019-9958(64)90223-2 . ​​Архивировано (PDF) из оригинала 2022-10-09.
9. Соломонофф, Рэй (июнь 1964 г.). "Формальная теория индуктивного вывода, часть II" (PDF) . Информация и управление . 7 (2): 224–254. doi : 10.1016/S0019-9958(64)90131-7 . Архивировано (PDF) из оригинала 2022-10-09.
10. Колмогоров, АН (1965). «Три подхода к количественному определению информации». Проблемы Информ. Передачи . 1 (1): 1–7. Архивировано из оригинала 28 сентября 2011 г.
11. Чайтин, Грегори Дж. (1969). «О простоте и скорости программ для вычисления бесконечных наборов натуральных чисел». Журнал ACM . 16 (3): 407–422. CiteSeerX 10.1.1.15.3821 . doi :10.1145/321526.321530. S2CID  12584692. 
12. Колмогоров, А. (1968). «Логические основы теории информации и теории вероятностей». Труды IEEE по теории информации . 14 (5): 662–664. doi :10.1109/TIT.1968.1054210. S2CID  11402549.
13. Ли, Мин; Витаний, Пол (2008). «Предварительные сведения». Введение в сложность Колмогорова и ее приложения . Тексты по информатике. стр. 1–99. doi :10.1007/978-0-387-49820-1_1. ISBN 978-0-387-33998-6.
14. Бургин, М. (1982). «Обобщенная колмогоровская сложность и двойственность в теории вычислений». Известия Российской академии наук . 25 (3): 19–23.
15. Хаттер, Маркус (2005). Универсальный искусственный интеллект: последовательные решения, основанные на алгоритмической вероятности . Тексты по теоретической информатике. Берлин Нью-Йорк: Springer. ISBN 978-3-540-26877-2.
16. Заявлено без доказательства в: PB Miltersen (2005). "Курсовые заметки по сжатию данных - сложность по Колмогорову" (PDF) . стр. 7. Архивировано из оригинала (PDF) 2009-09-09.
17. Звонкин, А.; Л. Левин (1970). «Сложность конечных объектов и разработка понятий информации и случайности средствами теории алгоритмов» (PDF) . Математические обзоры . 25 (6): 83–124. Bibcode :1970RuMaS..25...83Z. doi :10.1070/RM1970v025n06ABEH001269. S2CID  250850390.
18. Грегори Дж. Чайтин (июль 1974 г.). «Информационно-теоретические ограничения формальных систем» (PDF) . Журнал ACM . 21 (3): 403–434. doi :10.1145/321832.321839. S2CID  2142553.Здесь: Теория 4.1б
19. Calude, Cristian S. (12 сентября 2002 г.). Информация и случайность: алгоритмическая перспектива. Springer. ISBN 9783540434665.
20. Уоллес, CS; Доу, DL (1999). «Минимальная длина сообщения и сложность Колмогорова». Computer Journal . 42 (4): 270–283. CiteSeerX 10.1.1.17.321 . doi :10.1093/comjnl/42.4.270. 
21. Существует 2 ⁿ строк битов длины n , но только 2 ⁿ -1 строк битов короче, поэтому максимальное сжатие получается таким.
22. Мартин-Лёф, Пер (1966). «Определение случайных последовательностей». Информация и управление . 9 (6): 602–619. doi : 10.1016/s0019-9958(66)80018-9 .
23. Галатоло, Стефано; Хойруп, Матье; Рохас, Кристобаль (2010). «Эффективная символическая динамика, случайные точки, статистическое поведение, сложность и энтропия» (PDF) . Информация и вычисления . 208 : 23–41. arXiv : 0801.0209 . doi :10.1016/j.ic.2009.05.001. S2CID  5555443. Архивировано (PDF) из оригинала 2022-10-09.
24. Алексей Кальченко (2004). «Алгоритмы оценки информационного расстояния с применением в биоинформатике и лингвистике». arXiv : cs.CC/0404039 .
25. Cover, Thomas M.; Thomas, Joy A. (2006). Элементы теории информации (2-е изд.). Wiley-Interscience. ISBN 0-471-24195-4.
26. Чайтин, Г.; Арсланов, А.; Калуд, Кристиан С. (1995-09-01). «Сложность размера программы вычисляет проблему остановки». Bull. EATCS . S2CID  39718973.
27. Ли, Мин; Витаний, Пол (2008). Введение в сложность Колмогорова и ее приложения. Упражнение 2.7.7. Bibcode :2008ikca.book.....L. doi :10.1007/978-0-387-49820-1. ISBN 978-0-387-33998-6. ISSN  1868-0941. {{cite book}}: |journal=проигнорировано ( помощь )
28. Йорма Риссанен (2007). Информация и сложность в статистическом моделировании . Springer S. стр. 53. ISBN 978-0-387-68812-1.
29. Мин Ли; Пол МБ Витаньи (2009). Введение в колмогоровскую сложность и ее приложения . Спрингер. стр. 105–106. ISBN 978-0-387-49820-1.
30. Мин Ли; Пол МБ Витаньи (2009). Введение в колмогоровскую сложность и ее приложения . Спрингер. п. 119. ИСБН 978-0-387-49820-1.
31. Витаний, Пол МБ (2013). «Условная сложность Колмогорова и универсальная вероятность». Теоретическая информатика . 501 : 93–100. arXiv : 1206.0983 . doi : 10.1016/j.tcs.2013.07.009. S2CID  12085503.

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

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

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

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