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

Подотрасль теории информации и информатики

Алгоритмическая теория информации ( АИТ ) — это раздел теоретической компьютерной науки , который занимается взаимосвязью между вычислением и информацией вычислимо сгенерированных объектов (в отличие от стохастически сгенерированных), таких как строки или любые другие структуры данных . Другими словами, в алгоритмической теории информации показано, что вычислительная несжимаемость «имитирует» (за исключением константы, которая зависит только от выбранного универсального языка программирования) отношения или неравенства, обнаруженные в теории информации . ^[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] , что все эти концепции случайности различны.

(Соответствующие определения могут быть сделаны для алфавитов, отличных от набора .) ${\displaystyle \{0,1\}}$

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

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

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

"0101010101010101010101010101010101010101010101010101010101010101"

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

"1100100001100001110111101110110011111010010000100101011110010110"

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

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

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

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

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

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

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

• Алгоритмическая вероятность  – математический метод присвоения априорной вероятности данному наблюдению.Страницы, отображающие описания викиданных в качестве резерва
• Алгоритмически случайная последовательность  – Двоичная последовательность
• Константа Хайтина  – Вероятность остановки случайной компьютерной программы
• Вычислительная неразличимость  – в информатике, связь между двумя семействами распределений.
• Распределительный ансамбль  – последовательность распределений вероятностей или случайных величин.Страницы, отображающие описания викиданных в качестве резерва
• Эпистемология  – философское изучение знания
• Индуктивное рассуждение  – Метод логического рассуждения
• Индуктивная вероятность  – определение вероятности будущих событий на основе прошлых событий.
• Теорема об инвариантности
• Колмогоровская сложность  – Мера алгоритмической сложности
• Минимальная длина описания  – Принцип выбора модели
• Минимальная длина сообщения  – формальная информационная теория, перефразирующая принцип бритвы Оккама
• Псевдослучайный ансамбль
• Генератор псевдослучайных чисел  – термин, используемый в теоретической информатике и криптографии.
• Теория простоты  – когнитивная теорияСтраницы, отображающие описания викиданных в качестве резерва
• Теорема Шеннона о кодировании источника  – устанавливает пределы возможного сжатия данных.
• Теория индуктивного вывода Соломонова  – Математическая теория

Ссылки

1. Chaitin 1975
2. "Алгоритмическая теория информации". Архивировано из оригинала 23 января 2016 года . Получено 3 мая 2010 года .
3. или, для взаимной алгоритмической информации, информирование об алгоритмической сложности ввода вместе с самим вводом.
4. Calude 2013
5. Дауни, Родни Г.; Хиршфельдт, Денис Р. (2010). Алгоритмическая случайность и сложность. Springer. ISBN 978-0-387-68441-3.
6. Ли и Витаний 2013
7. Витаний, П. «Некролог: Рэй Соломонофф, отец-основатель алгоритмической теории информации»
8. Доклад с конференции «Церебральные системы и компьютеры», Калифорнийский технологический институт, 8–11 февраля 1960 г., цитируется в «Формальной теории индуктивного вывода», часть 1, 1964 г., стр. 1
9. Соломонофф, Р., «Предварительный отчет об общей теории индуктивного вывода», отчет V-131, Zator Co., Кембридж, Массачусетс, (ноябрьская редакция отчета от 4 февраля 1960 г.)
10. Ван, Юнге (1996). Случайность и сложность (PDF) (PhD). Гейдельбергский университет.

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

• Алгоритмическая теория информации в Scholarpedia
• Рассказ Хайтина об истории АИТ.

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

• Блюм, М. (1967). «О размерах машин». Информация и управление . 11 (3): 257–265. doi :10.1016/S0019-9958(67)90546-3.
• Блюм, М. (1967). «Машинно-независимая теория сложности рекурсивных функций». Журнал ACM . 14 (2): 322–336. doi : 10.1145/321386.321395 . S2CID  15710280.
• Бургин, М. (1982). «Обобщенная колмогоровская сложность и двойственность в теории вычислений». Докл. АН СССР. 25 ( 3): 19–23.
• Burgin, M. (1990). «Обобщенная сложность Колмогорова и другие меры двойной сложности». Cybernetics . 26 (4): 481–490. doi :10.1007/BF01068189. S2CID  121736453.
• Burgin, M. (2005). Суперрекурсивные алгоритмы. Монографии по информатике. Springer. ISBN 9780387955698.
• Calude, CS (1996). "Алгоритмическая теория информации: открытые проблемы" (PDF) . J. UCS . 2 (5): 439–441. Архивировано из оригинала (PDF) 28 ноября 2021 г. . Получено 30 июня 2019 г. .
• Calude, CS (2013). Информация и случайность: алгоритмическая перспектива. Тексты по теоретической информатике. Серия EATCS (2-е изд.). Springer-Verlag. ISBN 9783662049785.
• Чайтин, Г. Дж. (1966). «О длине программ для вычисления конечных двоичных последовательностей». Журнал Ассоциации вычислительной техники . 13 (4): 547–569. doi :10.1145/321356.321363. S2CID  207698337.
• Чайтин, Г. Дж. (1969). «О простоте и скорости программ для вычисления определенных множеств натуральных чисел». Журнал Ассоциации вычислительной техники . 16 (3): 407–412. doi : 10.1145/321526.321530 . S2CID  12584692.
• Чайтин, Г. Дж. (1975). «Теория размера программы, формально идентичная теории информации». Журнал Ассоциации вычислительной техники . 22 (3): 329–340. doi : 10.1145/321892.321894 . S2CID  14133389.
• Чайтин, Г. Дж. (1977). «Алгоритмическая теория информации». IBM Journal of Research and Development . 21 (4): 350–9. doi :10.1147/rd.214.0350.
• Чайтин, Г. Дж. (1987). Алгоритмическая теория информации . Cambridge University Press. ISBN 9780521343060.
• Колмогоров, А. Н. (1965). «Три подхода к определению количества информации». Проблемы передачи информации (1): 3–11.
• Колмогоров, АН (1968). «Логические основы теории информации и теории вероятностей». IEEE Trans. Inf. Theory . IT-14 (5): 662–4. doi :10.1109/TIT.1968.1054210. S2CID  11402549.
• Левин, Л.А. (1974). «Законы информации (нероста) и аспекты обоснования теории вероятностей». Проблемы передачи информации . 10 (3): 206–210.
• Левин, Л. А. (1976). «Различные меры сложности конечных объектов (аксиоматическое описание)». Докл . сов. матем. 17 : 522–526.
• Ли, М.; Витаний, П. (2013). Введение в сложность Колмогорова и ее приложения (2-е изд.). Springer-Verlag. ISBN 9781475726060.
• Solomonoff, RJ (1960). Предварительный отчет об общей теории индуктивного вывода (PDF) (Технический отчет). Кембридж, Массачусетс: Zator Company. ZTB-138.
• Соломонов, Р. Дж. (1964). «Формальная теория индуктивного вывода». Информация и управление . 7 (1): 1–22. doi : 10.1016/S0019-9958(64)90223-2 .
• Соломонов, Р. Дж. (1964). «Формальная теория индуктивного вывода». Информация и управление . 7 (2): 224–254. doi :10.1016/S0019-9958(64)90131-7.
• Solomonoff, RJ (2009). Emmert-Streib, F.; Dehmer, M. (ред.). Алгоритмическая вероятность: теория и приложения, теория информации и статистическое обучение . Springer. ISBN 978-0-387-84815-0.
• Ван Ламбаген (1989). "Алгоритмическая теория информации" (PDF) . Журнал символической логики . 54 (4): 1389–1400. doi :10.1017/S0022481200041153. S2CID  250348327.
• Zurek, WH (2018) [1991]. «Алгоритмическое информационное содержание, тезис Чёрча-Тьюринга, физическая энтропия и демон Максвелла, в». Сложность, энтропия и физика информации . Addison-Wesley. стр. 73–89. ISBN 9780429982514.
• Звонкин, А.К. и Левин, Л.А. (1970). «Сложность конечных объектов и разработка понятий информации и случайности средствами теории алгоритмов». Математические обзоры . 256 (6): 83–124. Bibcode :1970RuMaS..25...83Z. doi :10.1070/RM1970v025n06ABEH001269. S2CID  250850390.{{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )