Войти
Это изображение иллюстрирует часть множества Мандельброта фрактал. Простое сохранение 24-битного цвета каждого пикселя в этом изображении потребует 1,62 миллиона байтов, но небольшая компьютерная программа может воспроизвести эти 1,62 миллиона байтов, используя определение набора Мандельброта и координаты углов изображения. Таким образом, колмогоровская сложность необработанного файла, кодирующего это растровое изображение, намного меньше 1,62 миллиона байтов в любой прагматической модели вычислений. В теории алгоритмической информации (подполе информатика и математика ), колмогоровская сложность объекта, такого как кусок текста, - это длина самой короткой компьютерной программы (в заранее заданном язык программирования ), который производит объект в качестве вывода. Это мера вычислительных ресурсов, необходимых для определения объекта, и также известна как алгоритмическая сложность, сложность Соломонова – Колмогорова – Чайтина, сложность размера программы, описательная сложность или алгоритмическая энтропия . Он назван в честь Андрея Колмогорова, который впервые опубликовал эту статью в 1963 году.
Понятие колмогоровской сложности может использоваться для утверждения и доказательства невозможности результатов, аналогичных диагональный аргумент Кантора, теорема Гёделя о неполноте и проблема остановки Тьюринга. В частности, никакая программа P, вычисляющая нижнюю границу для каждой сложности Колмогорова текста, не может возвращать значение, существенно превышающее собственную длину P (см. Раздел § Теорема Чейтина о неполноте); следовательно, ни одна программа не может вычислить точную сложность Колмогорова для бесконечного множества текстов.
Рассмотрим следующие две строки из 32 строчных букв и цифр:
abababababababababababababababи4c1j5b2p0cv4w1x8rx2y39umg314q85s7 первая строка краткое описание на английском языке, а именно «напишите ab 16 раз», которое состоит из 17 символов. У второго нет очевидного простого описания (с использованием того же набора символов), кроме записи самой строки, то есть «write 4c1j5b2p0cv4w1x8rx2y39umgw5q85s7», которое содержит 38 символов. Следовательно, можно сказать, что операция записи первой строки «менее сложна», чем запись второй.
Более формально, сложность строки - это длина кратчайшего возможного описания строки на некотором фиксированном универсальном языке описания (чувствительность сложности относительно выбор языка описания обсуждается ниже). Можно показать, что колмогоровская сложность любой строки не может быть больше, чем на несколько байтов, больше длины самой строки. Строки, подобные приведенному выше примеру abab, чья колмогоровская сложность мала по сравнению с размером строки, не считаются сложными.
Сложность Колмогорова может быть определена для любого математического объекта, но для простоты объем данной статьи ограничен строками. Сначала мы должны указать язык описания для строк. Такой язык описания может быть основан на любом языке компьютерного программирования, таком как Lisp, Pascal или Java. Если P - это программа, которая выводит строку x, то P - это описание x. Длина описания - это просто длина P в виде строки символов, умноженная на количество бит в символе (например, 7 для ASCII ).
В качестве альтернативы мы могли бы выбрать кодировку для машин Тьюринга, где кодировка - это функция, которая связывает с каждой машиной Тьюринга M цепочку битов . Если M - машина Тьюринга, которая на входе w выводит строку x, то объединенная строка w является описанием x. Для теоретического анализа этот подход больше подходит для построения подробных формальных доказательств и обычно предпочитается в исследовательской литературе. В этой статье обсуждается неформальный подход.
Любая строка s имеет хотя бы одно описание. Например, вторая строка выше выводится программой:
function GenerateString2 () return "4c1j5b2p0cv4w1x8rx2y39umgw5q85s7"
, тогда как первая строка выводится (намного короче) псевдокод:
функция GenerateString1 () return "ab" × 16
Если описание d (s) строки s имеет минимальную длину (т.е., используя наименьшее количество битов), это называется минимальным описанием s, а длина d (s) (то есть количество битов в минимальном описании) составляет сложность Колмогорова of s, записывается K (s). Символически
- K (s) = | d (s) |.
Длина самого короткого описания будет зависеть от выбора языка описания; но эффект изменения языков ограничен (результат, называемый теоремой инвариантности).
Теорема инвариантности
Неформальная обработка
Существуют некоторые языки описания, которые являются оптимальными в следующем смысле: при любом описании объекта на языке описания указанное описание может использоваться на оптимальном языке описания с постоянными накладными расходами. Константа зависит только от задействованных языков, а не от описания объекта или самого объекта.
Вот пример оптимального языка описания. Описание будет состоять из двух частей:
- Первая часть описывает другой язык описания.
- Вторая часть - это описание объекта на этом языке.
В более технических терминах первая часть description - это компьютерная программа, вторая часть которой является входом для той компьютерной программы, которая производит объект в качестве выходного.
Теорема инвариантности следующая: Для любого языка описания L оптимальный язык описания по крайней мере так же эффективен, как L, с некоторыми постоянными накладными расходами.
Доказательство: Любое описание D в L может быть преобразовано в описание на оптимальном языке, сначала описав L как компьютерную программу P (часть 1), а затем используя исходное описание D в качестве входных данных для этой программы ( часть 2). Общая длина этого нового описания D ′ равна (приблизительно):
- | D ′ | = | P | + | D |
Длина P - это константа, не зависящая от D. Таким образом, существует не более постоянных накладных расходов, независимо от описываемого объекта. Следовательно, оптимальный язык универсален до этой аддитивной константы.
Более формальная трактовка
Теорема : Если K 1 и K 2 являются функциями сложности относительно полного Тьюринга языков описания L 1 и L 2, тогда существует константа c, которая зависит только от языков L 1 и L 2 выбранный - такой, что
- ∀s. −c ≤ K 1 (s) - K 2 (s) ≤ c.
Доказательство : по симметрии достаточно доказать, что существует некоторая константа c такая, что для всех строк s
- K1(s) ≤ K 2 (s) + c.
Теперь предположим, что существует программа на языке L 1, которая действует как интерпретатор для L 2:
, функция InterpretLanguage (string p)
, где p - программа в L 2. Интерпретатор характеризуется следующим свойством:
- Запуск
InterpretLanguageна входе p возвращает результат выполнения p.
Таким образом, если P является программой на L 2, которое является минимальным описанием s, тогда InterpretLanguage(P) возвращает строку s. Длина этого описания s равна сумме
- Длина программы
InterpretLanguage, которую мы можем принять за константу c. - Длина P, который по определению равен K 2 (s).
Это доказывает желаемую верхнюю границу.
История и контекст
Теория алгоритмической информации - это область компьютерных наук, изучающая сложность Колмогорова и другие меры сложности для строк (или других структур данных ).
Концепция и теория сложности Колмогорова основана на ключевой теореме, впервые открытой Рэем Соломоновым, который опубликовал ее в 1960 году, описав ее в «Предварительном отчете по общей теории индукции. Вывод »как часть его изобретения алгоритмической вероятности. Он дал более полное описание в своих публикациях 1964 года «Формальная теория индуктивного вывода», часть 1 и часть 2 в книге «Информация и управление».
Андрей Колмогоров позже независимо опубликовал эту теорему в Проблемы Информ. Передача в 1965 году. Григорий Чайтин также представляет эту теорему в J. ACM - статья Чайтина была представлена в октябре 1966 года и пересмотрена в декабре 1968 года, и цитирует работы Соломонова и Колмогорова.
В теореме говорится что среди алгоритмов, декодирующих строки по их описаниям (кодам), существует оптимальный. Этот алгоритм для всех строк позволяет использовать коды настолько короткие, насколько позволяет любой другой алгоритм, вплоть до аддитивной константы, которая зависит от алгоритмов, но не от самих строк. Соломонофф использовал этот алгоритм и длины кода, которые он позволяет определить «универсальную вероятность» строки, на которой может быть основан индуктивный вывод последующих цифр строки. Колмогоров использовал эту теорему для определения нескольких функций строк, включая сложность, случайность и информацию.
Когда Колмогоров узнал о работе Соломонова, он признал приоритет Соломонова. В течение нескольких лет работы Соломонова были лучше известны в Советском Союзе, чем в западном мире. Однако общее мнение в научном сообществе заключалось в том, чтобы связать этот тип сложности с Колмогоровым, который интересовался случайностью последовательности, в то время как алгоритм алгоритмической вероятности стал ассоциироваться с Соломоновым, который сосредоточился на прогнозировании с использованием своего изобретения универсального априорного распределения вероятностей.. Более широкая область, охватывающая сложность описания и вероятность, часто называется сложностью Колмогорова. Ученый-компьютерщик Мин Ли считает это примером эффекта Мэтью : «… каждому, у кого будет больше, будет дано…»
Есть несколько других вариантов сложности Колмогорова или алгоритмической информации. Наиболее широко используемый метод основан на Леониде Левине (1974), и в основном благодаря ему.
Аксиоматический подход к колмогоровской сложности, основанный на аксиомах Блюма (Blum 1967), был представлен Марком Бургином в статье, представленной для публикации Андреем Колмогоровым.
Основные результаты
Пусть в следующем обсуждении K (s) будет сложностью строки s.
Нетрудно увидеть, что минимальное описание строки не может быть слишком большим, чем сама строка - программа GenerateString2выше, которая выводит s, на фиксированное значение больше, чем s.
Теорема : существует константа c такая, что
- ∀s. K (s) ≤ | s | + c.
Невычислимость колмогоровской сложности
Наивная попытка программы вычислить K
На первый взгляд может показаться тривиальным написать программу, которая может вычислять K (s) для любые s, например следующие:
функция KolmogorovComplexity (string s) for i = 1 to infinity: для каждого строка p длиной ровно i if isValidProgram (p) и Assessment (p) == s return i
Эта программа выполняет итерацию через все возможные программы (путем перебора всех возможных строк и рассмотрения только тех, которые являются допустимыми программами), начиная с самой короткой. Каждая программа выполняется, чтобы найти результат, созданный этой программой, сравнивая его с вводом s. Если результат совпадает, возвращается длина программы.
Однако это не сработает, потому что некоторые из протестированных программ не завершаются, например если они содержат бесконечные циклы. Невозможно избежать всех этих программ, протестировав их каким-либо образом перед их выполнением из-за невычислимости проблемы остановки.
Более того, никакая программа вообще не может вычислить функцию K, быть он очень сложный. Это подтверждается следующим.
Формальное доказательство невычислимости K
Теорема : существуют строки сколь угодно большой колмогоровской сложности. Формально: для каждого n ∈ ℕ существует строка s с K (s) ≥ n.
Доказательство: В противном случае все бесконечное число возможных конечных строк могло бы быть сгенерировано конечным числом программ со сложностью ниже n бит.
Теорема : K не является вычислимой функцией. Другими словами, не существует программы, которая принимает любую строку s в качестве ввода и выдает целое число K (s) в качестве вывода.
Следующий непрямой proof использует простой Pascal -подобный язык для обозначения программ; для простоты доказательства предположим, что его описание (т.е. интерпретатор ) имеет длину 1400000 бит. Допустим, для противоречия существует программа
function KolmogorovComplexity (string s)
, которая принимает на входе строку s и возвращает K (s). Все программы имеют конечную длину, поэтому для простоты доказательства предположим, что она составляет 7000000000 бит. Теперь рассмотрим следующую программу длиной 1288 бит:
function GenerateComplexString () для i = 1 до бесконечности: для каждой строки s длины ровно i если KolmogorovComplexity (s) ≥ 8000000000 return s
Используя KolmogorovComplexityв качестве подпрограммы, программа пробует каждую строку, начиная с самый короткий, пока он не вернет строку с колмогоровской сложностью не менее 8000000000 бит, то есть строку, которая не может быть создана какой-либо программой короче 8000000000 бит. Однако общая длина приведенной выше программы, которая произвела s, составляет всего 7001401288 бит, что является противоречием. (Если код KolmogorovComplexityкороче, противоречие остается. Если он длиннее, константу, используемую в GenerateComplexString, всегда можно изменить соответствующим образом.)
Вышеуказанное доказательство использует противоречие, подобное противоречию парадокса Берри : «1 2 наименьшее 3 положительное 4 целое число 5, что 6 не может 7 быть 8 определено 9 в 10 меньше 11, чем 12 двадцать 13 английских 14 слов ". Также возможно показать невычислимость K путем сведения из невычислимости проблемы остановки H, поскольку K и H эквивалентны Тьюрингу.
Существует следствие, шутливо названное "теорема о полной занятости "в сообществе языков программирования, утверждающая, что не существует идеального компилятора, оптимизирующего размер.
Цепное правило для сложности Колмогорова
Цепное правило для сложности Колмогорова утверждает, что
- K (X, Y) ≤ K (X) + K (Y | X) + O (log (K (X, Y))).
В нем указано, что самая короткая программа, которая воспроизводит X и Y, не более, чем логарифмический член больше, чем программа для воспроизведения X и программа для воспроизведения Y с учетом X. Используя этот оператор, можно определить аналог взаимной информации для колмогоровской сложности.
Сжатие
Вычислить верхние границы для K (s) просто - просто compress строку s с помощью некоторого метода, реализовать соответствующий декомпрессор на выбранном языке, объединить декомпрессор со сжатой строкой и измерить длину результирующей строки - конкретно, размер самораспаковывающегося архива на данном языке.
Строка s может быть сжата числом c, если у нее есть описание, длина которого не превышает | s | - c бит. Это равносильно утверждению, что K (s) ≤ | s | - c. В противном случае 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 + 2.
Доказать теорему, обратите внимание, что количество описаний длиной не более n - c задается геометрическим рядом:
- 1 + 2 + 2 +… + 2 = 2 - 1.
Остается не менее
- 2 - 2 + 1
битовых цепочек длины n, несжимаемых c. Чтобы определить вероятность, разделите ее на 2.
Теорема Чайтина о неполноте
сложность Колмогорова K (s) и две вычислимые функции нижней границы prog1 (s), prog2 ( s). На горизонтальной оси (логарифмический масштаб ) перечислены все строки s, отсортированные по длине; вертикальная ось (линейная шкала ) измеряет сложность Колмогорова в битах. Большинство струн несжимаемы, т.е. их колмогоровская сложность на постоянную величину превышает их длину. На рисунке показаны 9 сжимаемых струн, которые выглядят почти вертикальными склонами. В соответствии с теоремой Чайтина о неполноте (1974 г.) результат любой программы, вычисляющей нижнюю границу сложности Колмогорова, не может превышать некоторый фиксированный предел, который не зависит от входной строки s. По указанной выше теореме (§ Сжатие), большинство строк сложны в том смысле, что их нельзя описать каким-либо значительно "сжатым" способом. Однако оказывается, что тот факт, что конкретная строка является сложной, невозможно формально доказать, если сложность строки превышает определенный порог. Точная формализация следующая. Во-первых, исправьте конкретную аксиоматическую систему Sдля натуральных чисел. Аксиоматическая система должна быть достаточно мощной, чтобы с некоторыми утверждениями A о сложности строк можно было связать формулу FAв S . Эта ассоциация должна обладать следующим свойством:
Если FAдоказуемо на основе аксиом S, то соответствующее утверждение A должно быть истинным. Эта «формализация» может быть достигнута на основе нумерации Гёделя.
Теорема : существует константа L (которая зависит только от S и от выбора языка описания) такая, что не существует строки s, для которой утверждение
- K (s) ≥ L (как формализовано в S)
, может быть доказано в рамках S.
Доказательство : Доказательство этого результата моделируется на само- ссылочная конструкция, использованная в парадоксе Берри.
Мы можем найти эффективное перечисление всех формальных доказательств в S с помощью некоторой процедуры
function NthProof (int n)
, который принимает в качестве входных данных n и выводит некоторое доказательство. Эта функция перечисляет все доказательства. Некоторые из них являются доказательствами для формул, которые нам здесь не нужны, поскольку все возможные доказательства на языке S производится для некоторого n. Некоторые из них являются формулами сложности вида K (s) ≥ n, где s и n - константы на языке S . Существует процедура
function NthProofProvesComplexityFormula (int n)
который определяет, действительно ли n-е доказательство доказывает формулу сложности K (s) ≥ L. Строки s и целое число L, в свою очередь, вычисляются с помощью процедуры:
function StringNthProof (int n)
function ComplexityLowerBoundNthProof (int n)
Рассмотрим следующую процедуру:
function GenerateProvablyComplexString (int n) для i = от 1 до бесконечности: если NthProofProvesComplexityFormula (i) и ComplexityLowerBoundNthProof (i) ≥ n return StringNthProof (i)
При заданном n эта процедура пробует каждое доказательство, пока не найдет строку и доказательство в формальной системе Sформулы K (s) ≥ L для некоторого L ≥ n; если такого доказательства не существует, цикл будет бесконечным.
Наконец, рассмотрим программу, состоящую из всех этих определений процедур и главного вызова:
GenerateProvablyComplexString (n 0)
, где константа n 0 будет определена позже on. Общая длина программы может быть выражена как U + log 2(n0), где U - некоторая константа, а log 2(n0) - длина целочисленного значения n 0 при разумном предположении, что он закодирован в двоичной системе счисления. Теперь рассмотрим функцию f: [2, ∞) → [1, ∞), определенную как f (x) = x - log 2 (x). Он строго возрастает на своей области определения и, следовательно, имеет обратный f: [1, ∞) → [2, ∞).
Определите n 0 = f (U) +1.
Тогда никакое доказательство формы «K (s) ≥L» с L≥n 0 не может быть получено в S, как видно из косвенный аргумент : если ComplexityLowerBoundNthProof (i)может вернуть значение ≥n 0, то цикл внутри GenerateProvablyComplexStringв конечном итоге завершится, и это процедура вернет строку s такую, что
K (s) ≥ n0 путем построения GenerateProvablyComplexString > U + log 2(n0) , поскольку n 0>f (U) подразумевает n 0 - log 2(n0) = f (n 0)>U ≥ K (s) , поскольку s был описан программой с этой длиной
Это противоречие, QED
Как следствие, указанная выше программа с выбранным значением n 0 должна выполняться бесконечно.
Подобные идеи используются для доказательства свойств константы Чейтина.
Минимальная длина сообщения
Принцип минимальной длины сообщения статистического и индуктивного вывода и машинного обучения был разработан CS Уоллес и Д. Бултоном в 1968 году. MML является байесовским (т. Е. Включает предыдущие убеждения) и основывается на теории информации. Он имеет желаемые свойства статистической инвариантности (то есть логический вывод преобразуется с повторной параметризацией, например, из полярных координат в декартовы координаты), статистической согласованности (т.е. даже для очень сложных задач MML сходится к любой базовой модели) и эффективности ( т.е. модель MML сходится к любой истинной базовой модели примерно так быстро, как это возможно). К.С. Уоллес, Д.Л. Доу (1999) показал формальную связь между MML и алгоритмической теорией информации (или колмогоровской сложностью).
Колмогоровская случайность
Колмогоровская случайность определяет строку (обычно из бит ) как random тогда и только тогда, когда он короче любой компьютерной программы, которая может создать эту строку. Чтобы уточнить это, необходимо указать универсальный компьютер (или универсальную машину Тьюринга), так что «программа» означает программу для этой универсальной машины. Случайная строка в этом смысле «несжимаема» в том смысле, что невозможно «сжать» строку в программу, длина которой меньше длины самой строки. Счетный аргумент используется, чтобы показать, что для любого универсального компьютера существует по крайней мере одна алгоритмически случайная строка каждой длины. Однако то, является ли какая-либо конкретная строка случайной, зависит от конкретного выбранного универсального компьютера.
Это определение может быть расширено, чтобы определить понятие случайности для бесконечных последовательностей из конечного алфавита. Эти алгоритмически случайные последовательности могут быть определены тремя эквивалентными способами. Один способ использует эффективный аналог теории меры ; другой использует эффективные мартингалы. Третий способ определяет бесконечную последовательность как случайную, если безпрефиксная колмогоровская сложность ее начальных сегментов растет достаточно быстро - должна быть константа c такая, что сложность начального сегмента длины n всегда была не меньше n - c. Это определение, в отличие от определения случайности для конечной строки, не зависит от того, какая универсальная машина используется для определения сложности Колмогорова без префиксов.
Отношение к энтропии
Для динамических систем энтропия Скорость и алгоритмическая сложность траекторий связаны теоремой Брудно, что равенство K (x; T) = h (T) выполняется почти для всех x.
Можно показать, что для выхода Марковские источники информации, колмогоровская сложность связана с энтропией источника информации. Точнее, колмогоровская сложность вывода марковского источника информации, нормированная на длину вывода, почти наверняка сходится (когда длина вывода стремится к бесконечности) к энтропии источника.
Условные версии
Условная колмогоровская сложность двух строк 
, грубо говоря, определяемая как колмогоровская сложность x, заданного y в качестве вспомогательного входа для процедуры.
Существует также условная сложность длины 
, который представляет собой сложность x с учетом длины x как известной / входной.
См. Также
- Важные публикации по теории алгоритмической информации
- Парадокс Берри
- Код гольф
- Сжатие данных
- Demoscene, дисциплина компьютерного искусства, определенные отрасли которой сосредоточены вокруг создания мельчайших программ, которые достигают определенных эффектов
- Теория описательной сложности
- Введение в грамматику
- Индуктивный вывод
- Структурная функция Колмогорова
- Расстояние Левенштейна
- Теория индуктивного вывода Соломонова
Примечания
Ссылки
Дополнительная литература
- Blum, M. (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). Алгоритмусок. TypoTeX. ISBN 963-279-014-6.
- Ли, Мин; Витани, Пол (1997). Введение в колмогоровскую сложность и ее приложения. Springer. ISBN 978-0387339986. CS1 maint: ref = harv (link )
- Ю., Манин (1977). Курс математической логики. Springer-Verlag. ISBN 978-0-7204-2844-5.
- Сипсер, Майкл (1997). Введение в теорию вычислений. PWS. ISBN 0-534-95097-3.
Внешние ссылки
- Наследие Андрея Николаевича Колмогорова
- Интернет-публикации Чайтина
- Страница IDSIA Соломонова
- Обобщения алгоритмических информация от Дж. Шмидхубер
- «Обзор Ли Витаньи 1997 г.».
- Тромп, Джон. «Игровая площадка для лямбда-исчисления Джона и комбинаторной логики».Компьютерная модель лямбда-исчисления Тромпа предлагает конкретное определение K ()]
- Универсальный AI на основе сложности Колмогорова ISBN 3-540-22139-5 от М. Хаттер : ISBN 3-540-22139-5
- страницы Дэвида Доу Минимальная длина сообщения (MML) и бритва Оккама. 337>Grunwald, P.; Pitt, MA (2005). Myung, IJ (ed.). Достижения в минимальной длине описания: теория и приложения. MIT Press. ISBN 0-262-07262-9.
сложность Колмогорова K (s) и две вычислимые функции нижней границы