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

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

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

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

Обзор

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

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

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

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

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

История

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

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

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

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

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

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

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

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

последовательность

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

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

"0101010101010101010101010101010101010101010101010101010101010101"

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

"1100100001100001110111101110110011111010010000100101011110010110"

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

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

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

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

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

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

См. также

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

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

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

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

• Блюм, М. (1967). «О размерах машин». Информация и контроль . 11 (3): 257–265. дои : 10.1016/S0019-9958(67)90546-3 .
• Блюм, М. (1967). «Машинно-независимая теория сложности рекурсивных функций» . Журнал АКМ . 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). Суперрекурсивные алгоритмы . Монографии по информатике. Спрингер. ISBN  9780387955698 .
• Калуд, CS (1996). «Алгоритмическая теория информации: открытые проблемы» (PDF) . Дж. УКС . 2 (5): 439–441. Архивировано из оригинала (PDF) 28 ноября 2021 года . Проверено 30 июня 2019 г.
• Калуд, CS (2013). Информация и случайность: алгоритмическая перспектива . Тексты по теоретической информатике. Серия EATCS (2-е изд.). Спрингер-Верлаг. 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). Алгоритмическая теория информации . Издательство Кембриджского университета. ISBN  9780521343060 .
• Колмогоров А.Н. (1965). «Три подхода к определению количества информации». Проблемы передачи информации (1): 3–11.
• Колмогоров А.Н. (1968). «Логические основы теории информации и теории вероятностей» . IEEE Транс. Инф. Теория . ИТ-14 (5): 662–4. дои : 10.1109/TIT.1968.1054210 . S2CID   11402549 .
• Левин, Луизиана (1974). «Законы информации (нероста) и аспекты основания теории вероятностей» . Проблемы передачи информации . 10 (3): 206–210.
• Левин, Луизиана (1976). «Различные меры сложности конечных объектов (аксиоматическое описание)» . Советская математика. Докл . 17 : 522–526.
• Ли, М.; Витаньи, П. (2013). Введение в колмогоровскую сложность и ее приложения (2-е изд.). Спрингер-Верлаг. ISBN  9781475726060 .
• Соломонов, Р.Дж. (1960). Предварительный отчет об общей теории индуктивного вывода (PDF) (технический отчет). Кембридж, Массачусетс: Компания Zator. ЗТБ-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). Эммерт-Штрайб, Ф.; Демер, М. (ред.). Алгоритмическая вероятность: теория и приложения, теория информации и статистическое обучение . Спрингер. ISBN  978-0-387-84815-0 .
• Ван Ламбаген (1989). «Алгоритмическая теория информации» (PDF) . Журнал символической логики . 54 (4): 1389–1400. дои : 10.1017/S0022481200041153 . S2CID   250348327 .
• Журек, WH (2018) [1991]. «Алгоритмическое информационное содержание, тезис Чёрча-Тьюринга, физическая энтропия и демон Максвелла» . Сложность, энтропия и физика информации . Аддисон-Уэсли. стр. 73–89. ISBN  9780429982514 .
• Звонкин А.К. и Левин Л.А. (1970). «Сложность конечных объектов и развитие концепций информации и случайности средствами теории алгоритмов». Российские математические обзоры . 256 (6): 83–124. Бибкод : 1970РуМаС..25...83З . дои : 10.1070/RM1970v025n06ABEH001269 . S2CID   250850390 . {{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )