Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

Обзор [ править ]

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

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

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

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

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

История [ править ]

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

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

Точные определения [ править ]

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

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

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

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

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

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

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

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

"0101010101010101010101010101010101010101010101010101010101010101"

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

"1100100001100001110111101110110011111010010000100101011110010110"

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

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

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

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

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

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

См. Также [ править ]

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

Ссылки [ править ]

  1. ^ а б Чайтин 1975
  2. ^ Алгоритмическая теория информации
  3. ^ или, для взаимной алгоритмической информации, информирование об алгоритмической сложности ввода вместе с самим вводом.
  4. ^ a b Калуде 2013
  5. ^ Дауни, Родни G .; Хиршфельдт, Денис Р. (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.
  • Бургин, М. (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 .