Алгоритмическая теория информации ( АИТ ) — это раздел теоретической компьютерной науки , который занимается взаимосвязью между вычислением и информацией вычислимо сгенерированных объектов (в отличие от стохастически сгенерированных), таких как строки или любые другие структуры данных . Другими словами, в алгоритмической теории информации показано, что вычислительная несжимаемость «имитирует» (за исключением константы, которая зависит только от выбранного универсального языка программирования) отношения или неравенства, обнаруженные в теории информации . [1] По словам Грегори Чайтина , это «результат помещения теории информации Шеннона и теории вычислимости Тьюринга в коктейльный шейкер и энергичного встряхивания». [2]
Помимо формализации универсальной меры для неприводимого информационного содержания вычислимо генерируемых объектов, некоторые основные достижения AIT заключались в том, чтобы показать, что: на самом деле алгоритмическая сложность следует (в самоограниченном случае) тем же неравенствам (за исключением константы [3] ), что и энтропия , как в классической теории информации; [1] случайность есть несжимаемость; [4] и, в области случайно генерируемого программного обеспечения, вероятность появления любой структуры данных имеет порядок кратчайшей программы, которая генерирует ее при запуске на универсальной машине. [5]
AIT в основном изучает меры неприводимого информационного содержания строк (или других структур данных ). Поскольку большинство математических объектов можно описать в терминах строк или как предел последовательности строк, его можно использовать для изучения широкого спектра математических объектов, включая целые числа . Одной из главных мотиваций AIT является само изучение информации, переносимой математическими объектами, как в области метаматематики , например, как показывают результаты неполноты, упомянутые ниже. Другие главные мотивы пришли из преодоления ограничений классической теории информации для отдельных и фиксированных объектов, формализации концепции случайности и нахождения осмысленного вероятностного вывода без предварительного знания распределения вероятностей (например, является ли оно независимым и одинаково распределенным , марковским или даже стационарным ). Таким образом, известно, что AIT в основном основан на трех основных математических концепциях и отношениях между ними: алгоритмическая сложность , алгоритмическая случайность и алгоритмическая вероятность . [6] [4]
Алгоритмическая теория информации в основном изучает меры сложности строк (или других структур данных ). Поскольку большинство математических объектов можно описать в терминах строк или как предел последовательности строк, ее можно использовать для изучения широкого спектра математических объектов, включая целые числа .
Неформально, с точки зрения алгоритмической теории информации, информационное содержание строки эквивалентно длине максимально сжатого возможного самодостаточного представления этой строки. Самодостаточное представление по сути является программой — на некотором фиксированном, но в остальном нерелевантном универсальном языке программирования — которая при запуске выводит исходную строку.
С этой точки зрения, 3000-страничная энциклопедия на самом деле содержит меньше информации, чем 3000 страниц совершенно случайных букв, несмотря на то, что энциклопедия гораздо полезнее. Это потому, что для реконструкции всей последовательности случайных букв нужно знать, что представляет собой каждая отдельная буква. С другой стороны, если бы из энциклопедии были удалены все гласные, кто-то с разумными знаниями английского языка мог бы ее реконструировать, так же как можно было бы, вероятно, реконструировать предложение "Ths sntnc hs lw nfrmtn cntnt" из контекста и присутствующих согласных.
В отличие от классической теории информации, алгоритмическая теория информации дает формальные , строгие определения случайной строки и случайной бесконечной последовательности , которые не зависят от физических или философских интуиций о недетерминизме или правдоподобии . (Набор случайных строк зависит от выбора универсальной машины Тьюринга, используемой для определения сложности Колмогорова , но любой выбор дает идентичные асимптотические результаты, поскольку сложность Колмогорова строки инвариантна с точностью до аддитивной константы, зависящей только от выбора универсальной машины Тьюринга. По этой причине набор случайных бесконечных последовательностей не зависит от выбора универсальной машины.)
Некоторые из результатов алгоритмической теории информации, такие как теорема Чайтина о неполноте , по-видимому, бросают вызов общепринятым математическим и философским интуициям. Наиболее примечательным среди них является построение константы Чайтина Ω , действительного числа, которое выражает вероятность того, что самоограничивающая универсальная машина Тьюринга остановится , когда ее входные данные будут предоставлены подбрасыванием честной монеты (иногда ее считают вероятностью того, что случайная компьютерная программа в конечном итоге остановится). Хотя Ω легко определяется, в любой последовательной аксиоматизируемой теории можно вычислить только конечное число цифр Ω , поэтому она в некотором смысле непознаваема , обеспечивая абсолютный предел знания, который напоминает теоремы Гёделя о неполноте . Хотя цифры Ω не могут быть определены, многие свойства Ω известны; например, это алгоритмически случайная последовательность , и, таким образом, ее двоичные цифры равномерно распределены (на самом деле она нормальна ).
Алгоритмическая теория информации была основана Рэем Соломоноффом [7] , который опубликовал основные идеи, на которых базируется эта область, как часть его изобретения алгоритмической вероятности — способа преодоления серьезных проблем, связанных с применением правил Байеса в статистике. Он впервые описал свои результаты на конференции в Калтехе в 1960 году [8] и в докладе в феврале 1960 года «Предварительный отчет об общей теории индуктивного вывода». [9] Алгоритмическая теория информации была позже разработана независимо Андреем Колмогоровым в 1965 году и Грегори Чайтиным около 1966 года.
Существует несколько вариантов сложности Колмогорова или алгоритмической информации; наиболее широко используемый из них основан на самоограничивающих программах и в основном принадлежит Леониду Левину (1974). Пер Мартин-Лёф также внес значительный вклад в теорию информации бесконечных последовательностей. Аксиоматический подход к алгоритмической теории информации, основанный на аксиомах Блюма (Blum 1967), был представлен Марком Бургиным в статье, представленной для публикации Андреем Колмогоровым (Burgin 1982). Аксиоматический подход охватывает другие подходы в алгоритмической теории информации. Можно рассматривать различные меры алгоритмической информации как частные случаи аксиоматически определенных мер алгоритмической информации. Вместо того, чтобы доказывать похожие теоремы, такие как основная теорема об инвариантности, для каждой конкретной меры, можно легко вывести все такие результаты из одной соответствующей теоремы, доказанной в аксиоматической постановке. Это общее преимущество аксиоматического подхода в математике. Аксиоматический подход к алгоритмической теории информации получил дальнейшее развитие в книге (Бергин 2005) и был применен к метрикам программного обеспечения (Бергин и Дебнат, 2003; Дебнат и Бергин, 2003).
Двоичная строка называется случайной, если ее колмогоровская сложность не меньше длины строки. Простой подсчет показывает, что некоторые строки любой заданной длины случайны, и почти все строки очень близки к случайности. Поскольку колмогоровская сложность зависит от фиксированного выбора универсальной машины Тьюринга (неформально, фиксированного «языка описания», на котором даны «описания»), набор случайных строк зависит от выбора фиксированной универсальной машины. Тем не менее, набор случайных строк в целом имеет схожие свойства независимо от фиксированной машины, поэтому можно (и часто так и происходит) говорить о свойствах случайных строк как группы без необходимости предварительного указания универсальной машины.
Говорят, что бесконечная двоичная последовательность случайна, если для некоторой константы c для всех n колмогоровская сложность начального сегмента длины n последовательности не меньше n − c . Можно показать, что почти каждая последовательность (с точки зрения стандартной меры — «честной монеты» или меры Лебега — на пространстве бесконечных двоичных последовательностей) случайна. Кроме того, поскольку можно показать, что колмогоровская сложность относительно двух различных универсальных машин отличается не более чем на константу, набор случайных бесконечных последовательностей не зависит от выбора универсальной машины (в отличие от конечных строк). Это определение случайности обычно называют случайностью Мартина-Лёфа , в честь Пера Мартина-Лёфа , чтобы отличить его от других подобных понятий случайности. Иногда его также называют 1-случайностью, чтобы отличить его от других более сильных понятий случайности (2-случайность, 3-случайность и т. д.). Помимо концепций случайности Мартина-Лёфа существуют также рекурсивная случайность, случайность Шнорра, случайность Курца и т. д. Юнге Ван показал [10] , что все эти концепции случайности различны.
(Соответствующие определения могут быть сделаны для алфавитов, отличных от набора .)
Алгоритмическая теория информации (АИТ) — это информационная теория отдельных объектов, использующая информатику и изучающая взаимосвязь между вычислениями, информацией и случайностью.
Информационное содержание или сложность объекта можно измерить длиной его самого короткого описания. Например, строка
"0101010101010101010101010101010101010101010101010101010101010101"
имеет краткое описание "32 повторения '01'", в то время как
"1100100001100001110111101110110011111010010000100101011110010110"
предположительно, не имеет простого описания, кроме записи самой строки.
Более формально алгоритмическая сложность (АС) строки x определяется как длина самой короткой программы, которая вычисляет или выводит x , где программа выполняется на некотором фиксированном эталонном универсальном компьютере.
Тесно связанным понятием является вероятность того, что универсальный компьютер выведет некоторую строку x , когда ему будет предоставлена программа, выбранная случайным образом. Эта алгоритмическая "соломоновская" вероятность (AP) является ключевой в решении старой философской проблемы индукции формальным способом.
Главным недостатком AC и AP является их невычислимость. Ограниченная по времени сложность "Levin" наказывает медленную программу, добавляя логарифм времени ее выполнения к ее длине. Это приводит к вычислимым вариантам AC и AP, а универсальный поиск "Levin" (US) решает все проблемы инверсии за оптимальное время (за исключением некоторой нереалистично большой мультипликативной константы).
AC и AP также допускают формальное и строгое определение случайности отдельных строк, не зависящее от физических или философских интуиций о недетерминизме или правдоподобии. Грубо говоря, строка является алгоритмически "Мартин-Лёфовской" случайной (AR), если она несжимаема в том смысле, что ее алгоритмическая сложность равна ее длине.
AC, AP и AR являются основными субдисциплинами AIT, но AIT проникает во многие другие области. Он служит основой принципа минимальной длины описания (MDL), может упростить доказательства в теории вычислительной сложности , использовался для определения универсальной метрики подобия между объектами, решает проблему демона Максвелла и многие другие.
{{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )