Алгоритмическая теория информации - Algorithmic information theory

Алгоритмическая теория информации (AIT) - это отрасль теоретической информатики, которая занимается отношениями между вычислениями и информацией о вычислимых объектах (в отличие от стохастически генерируемых), таких как строки или любая другая структура данных . Другими словами, в рамках алгоритмической теории информации показано, что вычислительная несжимаемость «имитирует» (за исключением константы, которая зависит только от выбранного универсального языка программирования) отношения или неравенства, обнаруженные в теории информации . По словам Грегори Чейтина , это «результат того, что теория информации Шеннона и теория вычислимости Тьюринга были помещены в коктейльный шейкер и сильно встряхнули».

Помимо формализации универсальной меры для неприводимого информационного содержания вычислимых объектов, некоторые основные достижения AIT заключались в том, чтобы показать, что: на самом деле алгоритмическая сложность следует (в случае с самоограничением ) тем же неравенствам (за исключением константы), которые энтропия делает, как в классической теории информации; случайность - несжимаемость; а в области случайно сгенерированного программного обеспечения вероятность появления любой структуры данных порядка самой короткой программы, которая ее генерирует при работе на универсальной машине.

AIT в основном изучает меры несводимого информационного содержания строк (или других структур данных ). Поскольку большинство математических объектов можно описать в терминах строк или как предел последовательности строк, его можно использовать для изучения широкого спектра математических объектов, включая целые числа . Одним из основных мотивов AIT является само изучение информации, переносимой математическими объектами, как , например, в области метаматематики , как показывают результаты неполноты, упомянутые ниже. Другие основные мотивы исходили от: преодоления ограничений классической теории информации для отдельных и фиксированных объектов; формализация понятия случайности ; и нахождение значимого вероятностного вывода без предварительного знания распределения вероятностей (например, является ли оно независимым и одинаково распределенным , марковским или даже стационарным ). Таким образом, известно, что в основе AIT лежат три основных математических понятия и взаимосвязи между ними: алгоритмическая сложность , алгоритмическая случайность и алгоритмическая вероятность .

Обзор

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

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

С этой точки зрения энциклопедия на 3000 страниц на самом деле содержит меньше информации, чем 3000 страниц совершенно случайных букв, несмотря на то, что энциклопедия намного полезнее. Это потому, что для восстановления всей последовательности случайных букв нужно знать, что такое каждая буква. С другой стороны, если бы все гласные были удалены из энциклопедии, кто-то с достаточным знанием английского языка мог бы восстановить их, так же как можно было бы восстановить предложение «Ths sntnc hs lw nfrmtn cntnt» из контекста и присутствующих согласных.

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

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

История

Теория алгоритмической информации была основана Рэем Соломоновым , который опубликовал основные идеи, на которых основана данная область, как часть своего изобретения алгоритмической вероятности - способа преодоления серьезных проблем, связанных с применением правил Байеса в статистике. Впервые он описал свои результаты на конференции в Калифорнийском технологическом институте в 1960 г. и в отчете от февраля 1960 г. «Предварительный отчет по общей теории индуктивного вывода». Позднее алгоритмическая теория информации была независимо разработана Андреем Колмогоровым в 1965 году и Григорием Чайтиным примерно в 1966 году.

Существует несколько вариантов колмогоровской сложности или алгоритмической информации; наиболее широко используемый основан на программах с самоограничением и в основном принадлежит Леониду Левину (1974). Пер Мартин-Лёф также внес значительный вклад в теорию информации бесконечных последовательностей. Аксиоматический подход к алгоритмической теории информации, основанный на аксиомах Блюма (Blum 1967), был представлен Марком Бургином в статье, представленной для публикации Андреем Колмогоровым (Burgin 1982). Аксиоматический подход включает в себя другие подходы в алгоритмической теории информации. Можно рассматривать различные меры алгоритмической информации как частные случаи аксиоматически определенных мер алгоритмической информации. Вместо того, чтобы доказывать аналогичные теоремы, такие как основная теорема инвариантности, для каждой конкретной меры, можно легко вывести все такие результаты из одной соответствующей теоремы, доказанной в аксиоматической постановке. Это общее преимущество аксиоматического подхода в математике. Аксиоматический подход к алгоритмической теории информации получил дальнейшее развитие в книге (Burgin 2005) и был применен к программным метрикам (Burgin and Debnath, 2003; Debnath and Burgin, 2003).

Точные определения

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

Бесконечная двоичная последовательность называется случайным , если для некоторой константы C , для всех п , то Колмогоров сложность начального отрезка длины п последовательности по меньшей мере , п  -  с . Можно показать, что почти всякая последовательность (с точки зрения стандартной меры - «честной монеты» или меры Лебега - на пространстве бесконечных двоичных последовательностей) случайна. Кроме того, поскольку можно показать, что сложность Колмогорова относительно двух различных универсальных машин отличается не более чем на константу, набор случайных бесконечных последовательностей не зависит от выбора универсальной машины (в отличие от конечных строк). Это определение случайности обычно называют случайностью Мартина-Лёфа в честь Пера Мартина-Лёфа , чтобы отличить его от других подобных понятий случайности. Его также иногда называют 1-случайностью, чтобы отличить его от других более сильных понятий случайности (2-случайность, 3-случайность и т. Д.). Помимо концепций случайности Мартина-Лёфа, существуют также рекурсивная случайность, случайность Шнорра, случайность Курца и т. Д. Юнгге Ван показал, что все эти концепции случайности различны.

(Связанные определения могут быть даны для алфавитов, отличных от набора .)

Конкретная последовательность

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

Информационное содержание или сложность объекта можно измерить по длине его кратчайшего описания. Например, строка

"0101010101010101010101010101010101010101010101010101010101010101"

имеет краткое описание «32 повторения '01'», а

"1100100001100001110111101110110011111010010000100101011110010110"

предположительно не имеет простого описания, кроме записи самой строки.

Более формально алгоритмическая сложность (AC) строки x определяется как длина самой короткой программы, которая вычисляет или выводит x , где программа выполняется на некотором фиксированном эталонном универсальном компьютере.

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

Главный недостаток AC и AP - их несчетность. Ограниченная по времени сложность «Левина» наказывает медленную программу, добавляя логарифм времени ее выполнения к ее длине. Это приводит к вычислимым вариантам AC и AP, а универсальный поиск «Левин» (US) решает все задачи обращения за оптимальное время (за исключением некоторой нереально большой мультипликативной константы).

AC и AP также позволяют формальное и строгое определение случайности отдельных строк, чтобы не зависеть от физических или философских интуиций о недетерминировании или вероятности. Грубо говоря, строка является алгоритмической случайностью Мартина-Лёфа (AR), если она несжимаема в том смысле, что ее алгоритмическая сложность равна ее длине.

AC, AP и AR являются основными дисциплинами AIT, но AIT появляется во многих других областях. Он служит основой принципа минимальной длины описания (MDL), может упростить доказательства в теории вычислительной сложности , использовался для определения универсальной метрики сходства между объектами, решает проблему демона Максвелла и многие другие.

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

использованная литература

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

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