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

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

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

Таким образом, известно, что в основе AIT лежат три основных математических понятия и отношения между ними: алгоритмическая сложность, алгоритмическая случайность, и алгоритмическая вероятность.^[3][4]

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

Обзор

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

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

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

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

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

История

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

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

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

Основная статья: Колмогоровская сложность

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

Основная статья: Алгоритмически случайная последовательность

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

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

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

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

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

"0101010101010101010101010101010101010101010101010101010101010101"

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

"1100100001100001110111101110110011111010010000100101011110010110"

по-видимому, не имеет простого описания, кроме записи самой строки.

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

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

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

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

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

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

• Алгоритмическая вероятность
• Алгоритмически случайная последовательность
• Постоянная Чайтина
• Случайность Чайтина – Колмогорова
• Вычислительно неразличимый
• Дистрибьюторский ансамбль
• Эпистемология
• Индуктивный вывод
• Индуктивная вероятность
• Теорема инвариантности
• Колмогоровская сложность
• Пределы знаний
• Минимальная длина описания
• Минимальная длина сообщения
• Псевдослучайный ансамбль
• Псевдослучайный генератор
• Теория простоты
• Теория индуктивного вывода Соломонова
• Форменный ансамбль

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

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

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

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

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

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