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

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

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

Определение [ править ]

Рассмотрим следующие две строки из 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

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

K ( s ) = | d ( s ) |,

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

Теорема инвариантности [ править ]

Неформальное обращение [ править ]

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

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

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

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

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

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

| D ′ | = | P | + | D |

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

Более формальное обращение [ править ]

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

∀ с . - c ≤ K 1 ( s ) - K 2 ( s ) ≤ c .

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

K 1 ( s ) ≤ K 2 ( s ) + c .

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

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

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

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

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

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

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

История и контекст [ править ]

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

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

Позднее Андрей Колмогоров независимо опубликовал эту теорему в Problems Inform. Передача [6] в 1965 г. Григорий Чайтин также представляет эту теорему в J. ACM  - статья Чайтина была представлена ​​в октябре 1966 г. и пересмотрена в декабре 1968 г. и цитирует работы Соломонова и Колмогорова. [7]

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

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

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

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

Основные результаты [ править ]

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

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

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

∀ с . K ( s ) ≤ | s | + c .

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

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

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

Функция колмогоровская сложность ( строка s) для I = 1 до бесконечности: для каждой строки р от длины точно я , если isValidProgram (р) и оценки (р) == ы возврата я

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

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

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

Формальное доказательство невычислимости 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 до бесконечности: для каждой струны сек от длины именно я , если это колмогоровская сложность (ы) ≥ 8000000000 возвратных сек

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

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

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

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

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

Цепное правило [12] для сложности Колмогорова утверждает, что

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

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

Сжатие [ править ]

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

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

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

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

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

1 + 2 + 2 2 +… + 2 n - c = 2 n - c +1 - 1.

Осталось не менее

2 п - 2 н - с +1 + 1

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

Теорема Чайтина о неполноте [ править ]

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

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

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

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

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

может быть доказано в рамках S . [13] : Thm.4.1b

Доказательство . Доказательство этого результата моделируется на основе самореференциальной конструкции, использованной в парадоксе Берри .

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

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

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

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

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

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

GenerateProvablyComplexString ( n 0 )

где постоянная n 0 будет определена позже. Общая длина программы может быть выражена как U + log 2 ( n 0 ), где U - некоторая константа, а log 2 ( n 0 ) представляет длину целочисленного значения n 0 , при разумном предположении, что оно закодировано в двоичных цифрах. . Теперь рассмотрим функцию f : [2, ∞) → [1, ∞), определенную формулой f ( x ) = x - log 2 ( x ). Она строго возрастаетна его области определения и, следовательно, имеет обратный f −1 : [1, ∞) → [2, ∞).

Определим n 0 = f −1 ( U ) +1.

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

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

Противоречие, QED

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

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

Минимальная длина сообщения [ править ]

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

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

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

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

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

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

Связь с энтропией [ править ]

Для динамических систем скорость энтропии и алгоритмическая сложность траекторий связаны теоремой Брудно о том, что равенство выполняется почти для всех . [16]

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

Условные версии [ править ]

Условная колмогоровская сложность двух строк , грубо говоря, определяется как колмогоровская сложность x, заданного y в качестве вспомогательного входа для процедуры. [18] [19]

Существует также сложность , зависящая от длины , которая представляет собой сложность x при длине x как известная / входная. [20] [21]

См. Также [ править ]

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

Заметки [ править ]

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

Ссылки [ править ]

  1. ↑ Колмогоров, Андрей (1963). «О таблицах случайных чисел». Sankhyā Ser. . 25 : 369–375. Руководство по ремонту  0178484 .
  2. ^ Колмогоров, Андрей (1998). «О таблицах случайных чисел». Теоретическая информатика . 207 (2): 387–395. DOI : 10.1016 / S0304-3975 (98) 00075-9 . Руководство по ремонту 1643414 . 
  3. ↑ Соломонов, Рэй (4 февраля 1960 г.). Предварительный отчет по общей теории индуктивного вывода (PDF) . Report V-131 (Отчет). Редакция опубликована в ноябре 1960 г.
  4. ^ Соломонов, Рэй (март 1964). «Формальная теория индуктивного вывода, часть I» (PDF) . Информация и контроль . 7 (1): 1-22. DOI : 10.1016 / S0019-9958 (64) 90223-2 .
  5. ↑ Соломонов, Рэй (июнь 1964 г.). "Формальная теория индуктивного вывода, часть II" (PDF) . Информация и контроль . 7 (2): 224–254. DOI : 10.1016 / S0019-9958 (64) 90131-7 .
  6. ↑ Колмогоров, АН (1965). «Три подхода к количественному определению информации» . Проблемы Информ. Трансмиссия . 1 (1): 1–7. Архивировано из оригинального 28 сентября 2011 года.
  7. ^ Хайтина, Gregory J. (1969). «О простоте и скорости программ для вычисления бесконечных множеств натуральных чисел». Журнал ACM . 16 (3): 407–422. CiteSeerX 10.1.1.15.3821 . DOI : 10.1145 / 321526.321530 . 
  8. ↑ Колмогоров, А. (1968). «Логические основы теории информации и теории вероятностей». IEEE Transactions по теории информации . 14 (5): 662–664. DOI : 10.1109 / TIT.1968.1054210 .
  9. ^ Ли, Мин; Витани, Пол (2008). «Отборочные». Введение в колмогоровскую сложность и ее приложения . Тексты по информатике. стр.  1 -99. DOI : 10.1007 / 978-0-387-49820-1_1 . ISBN 978-0-387-33998-6.
  10. ^ Бургин М. (1982), "Обобщенная колмогоровская сложность и двойственность в теории вычислений", Извещения Российской Академии Наук , т.25, № 3, стр. 19–23.
  11. ^ Заявлены без доказательства в: «примечаниях курса для сжатия данных - Колмогоров сложности» Архивированных 2009-09-09 в Wayback Machine , 2005, PB Miltersen, с.7
  12. ^ Звонкин, А .; Л. Левин (1970). «Сложность конечных объектов и развитие понятий информации и случайности с помощью теории алгоритмов» (PDF) . Российские математические обзоры . 25 (6). С. 83–124.
  13. ↑ Грегори Дж. Чайтин (июль 1974 г.). "Теоретико-информационные ограничения формальных систем" (PDF) . Журнал ACM . 21 (3): 403–434. DOI : 10.1145 / 321832.321839 .
  14. ^ Уоллес, CS; Доу, Д.Л. (1999). «Минимальная длина сообщения и колмогоровская сложность». Компьютерный журнал . 42 (4): 270–283. CiteSeerX 10.1.1.17.321 . DOI : 10.1093 / comjnl / 42.4.270 . 
  15. ↑ Мартин-Лёф, Пер (1966). «Определение случайных последовательностей» . Информация и контроль . 9 (6): 602–619. DOI : 10.1016 / s0019-9958 (66) 80018-9 .
  16. ^ Галатоло, Стефано; Хойруп, Матьё; Рохас, Кристобаль (2010). «Эффективная символическая динамика, случайные точки, статистическое поведение, сложность и энтропия» (PDF) . Информация и вычисления . 208 : 23–41. DOI : 10.1016 / j.ic.2009.05.001 .
  17. ^ Алексей Kaltchenko (2004). «Алгоритмы оценки информационного расстояния применительно к биоинформатике и лингвистике». arXiv : cs.CC/0404039 .
  18. ↑ Йорма Риссанен (2007). Информация и сложность статистического моделирования . Спрингер С. п. 53 . ISBN 978-0-387-68812-1.
  19. ^ Мин Ли; Пол МБ Витани (2009). Введение в колмогоровскую сложность и ее приложения . Springer. стр.  105 -106. ISBN 978-0-387-49820-1.
  20. ^ Мин Ли; Пол МБ Витани (2009). Введение в колмогоровскую сложность и ее приложения . Springer. п. 119 . ISBN 978-0-387-49820-1.
  21. ^ Vitányi, Пол MB (2013). «Условная колмогоровская сложность и универсальная вероятность» . Теоретическая информатика . 501 : 93–100. arXiv : 1206.0983 . DOI : 10.1016 / j.tcs.2013.07.009 .

Дальнейшее чтение [ править ]

  • Блюм, М. (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.
  • Ю., Манин (1977). Курс математической логики . Springer-Verlag. ISBN 978-0-7204-2844-5.
  • Сипсер, Майкл (1997). Введение в теорию вычислений . PWS. ISBN 0-534-95097-3.

Внешние ссылки [ править ]

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