Алгоритмическая теория информации - 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), может упростить доказательства в теории вычислительной сложности , использовался для определения универсальной метрики сходства между объектами, решает проблему демона Максвелла и многие другие.
Смотрите также
- Алгоритмическая вероятность
- Алгоритмически случайная последовательность
- Постоянная Чайтина
- Случайность Чайтина – Колмогорова.
- Вычислительно неразличимый
- Дистрибьюторский ансамбль
- Эпистемология
- Индуктивный вывод
- Индуктивная вероятность
- Теорема инвариантности
- Колмогоровская сложность
- Пределы знаний
- Минимальная длина описания
- Минимальная длина сообщения
- Псевдослучайный ансамбль
- Псевдослучайный генератор
- Теория простоты
- Теория индуктивного вывода Соломонова
- Форменный ансамбль
использованная литература
внешние ссылки
дальнейшее чтение
- Блюм, М. (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.
- Бургин, М. (1990). "Обобщенная колмогоровская сложность и другие двойственные меры сложности". Кибернетика . 26 (4): 481–490. DOI : 10.1007 / BF01068189 . S2CID 121736453 .
- Бургин, М. (2005). Суперрекурсивные алгоритмы . Монографии по информатике. Springer. ISBN 9780387955698.
- Калуд, CS (1996). «Алгоритмическая теория информации: открытые проблемы» (PDF) . J. UCS . 2 (5): 439–441.
- Калуд, CS (2013). Информация и случайность: алгоритмическая перспектива . Тексты по теоретической информатике. Серия EATCS (2-е изд.). Springer-Verlag. ISBN 9783662049785.
- Чайтин, GJ (1966). «О длине программ для вычисления конечных двоичных последовательностей». Журнал Ассоциации вычислительной техники . 13 (4): 547–569. DOI : 10.1145 / 321356.321363 . S2CID 207698337 .
- Чайтин, GJ (1969). «О простоте и скорости программ для вычисления определенных множеств натуральных чисел». Журнал Ассоциации вычислительной техники . 16 (3): 407–412. DOI : 10.1145 / 321526.321530 . S2CID 12584692 .
- Чайтин, GJ (1975). "Теория размера программы, формально идентичная теории информации". Журнал Ассоциации вычислительной техники . 22 (3): 329–340. DOI : 10.1145 / 321892.321894 . S2CID 14133389 .
- Чайтин, GJ (1977). «Алгоритмическая теория информации». Журнал исследований и разработок IBM . 21 (4): 350–9. DOI : 10.1147 / rd.214.0350 .
- Чайтин, GJ (1987). Алгоритмическая теория информации . Издательство Кембриджского университета.
- Колмогоров, АН (1965). «Три подхода к определению количества информации». Проблемы передачи информации (1): 3–11.
- Колмогоров, АН (1968). «Логические основы теории информации и теории вероятностей» . IEEE Trans. Инф. Теория . ИТ-14 (5): 662–4. DOI : 10.1109 / TIT.1968.1054210 .
- Левин, Л.А. (1974). «Законы информации (нерастания) и аспекты основания теории вероятностей» . Проблемы передачи информации . 10 (3): 206–210.
- Левин, Л.А. (1976). «Различные меры сложности для конечных объектов (аксиоматическое описание)» . Советская математика. Докл . 17 : 522–526.
- Li, M .; Витани, П. (2013). Введение в колмогоровскую сложность и ее приложения (2-е изд.). Springer-Verlag. ISBN 9781475726060.
- Соломонов, RJ (1960). Предварительный отчет по общей теории индуктивного вывода (PDF) (Технический отчет). Кембридж, Массачусетс: Zator Company. ЗТБ-138.
- Соломонов, RJ (1964). «Формальная теория индуктивного вывода» . Информация и контроль . 7 (1): 1-22. DOI : 10.1016 / S0019-9958 (64) 90223-2 .
- Соломонов, RJ (1964). «Формальная теория индуктивного вывода» . Информация и контроль . 7 (2): 224–254. DOI : 10.1016 / S0019-9958 (64) 90131-7 .
- Соломонов, RJ (2009). Emmert-Streib, F .; Демер М. (ред.). Алгоритмическая вероятность: теория и приложения, теория информации и статистическое обучение . Springer. ISBN 978-0-387-84815-0.
- Ван Ламбаген (1989). «Алгоритмическая теория информации» (PDF) . Журнал символической логики . 54 (4): 1389–1400. DOI : 10.1017 / S0022481200041153 .
- Зурек, WH (2018) [1991]. «Алгоритмическое информационное содержание, тезис Черча-Тьюринга, физическая энтропия и демон Максвелла» . Сложность, энтропия и физика информации . Эддисон-Уэсли. С. 73–89. ISBN 9780429982514.
- Звонкин А.К., Левин Л.А. (1970). «Сложность конечных объектов и развитие представлений об информации и случайности средствами теории алгоритмов». Российские математические обзоры . 256 (6): 83–124. Bibcode : 1970RuMaS..25 ... 83Z . DOI : 10.1070 / RM1970v025n06ABEH001269 .