Алгоритмическая теория информации (AIT) — это раздел теоретической информатики , который занимается взаимосвязью между вычислениями и информацией о вычислимо генерируемых объектах (в отличие от стохастически генерируемых), таких как строки или любые другие структуры данных . Другими словами, в рамках алгоритмической теории информации показано, что вычислительная несжимаемость «имитирует» (за исключением константы, которая зависит только от выбранного универсального языка программирования) отношения или неравенства, обнаруженные в теории информации . [1] По словам Грегори Чайтина , это «результат помещения теории информации Шеннона и теории вычислимости Тьюринга в шейкер и энергичного встряхивания» . [2]
Помимо формализации универсальной меры несократимого информационного содержания вычислимо генерируемых объектов, некоторые основные достижения МТА заключались в том, чтобы показать, что: на самом деле алгоритмическая сложность следует (в самоограниченном случае ) из тех же неравенств (за исключением константы [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] , что все эти концепции случайности различны.
(Соответствующие определения могут быть сделаны для алфавитов, отличных от набора .)
Алгоритмическая теория информации (AIT) — это теория информации об отдельных объектах, использующая информатику и изучающая взаимосвязь между вычислениями, информацией и случайностью.
Информативность или сложность объекта можно измерить длиной его кратчайшего описания. Например, строка
"0101010101010101010101010101010101010101010101010101010101010101"
имеет краткое описание «32 повторения '01'», а
"1100100001100001110111101110110011111010010000100101011110010110"
предположительно не имеет простого описания, кроме записи самой строки.
Более формально, алгоритмическая сложность (AC) строки x определяется как длина кратчайшей программы, которая вычисляет или выводит x , где программа запускается на некотором универсальном компьютере с фиксированной ссылкой.
Близкое к этому понятие — это вероятность того, что универсальный компьютер выдаст некоторую строку x , если ему будет передана случайно выбранная программа. Эта алгоритмическая «соломоновская» вероятность (AP) является ключом к формальному решению старой философской проблемы индукции.
Основным недостатком AC и AP является их неисчислимость. Ограниченная по времени сложность «Левина» наказывает медленную программу добавлением логарифма времени ее выполнения к ее длине. Это приводит к вычислимым вариантам AC и AP, а универсальный поиск «Левина» (США) решает все задачи инверсии за оптимальное время (кроме некоторой нереально большой мультипликативной константы).
AC и AP также позволяют формально и строго определить случайность отдельных строк, чтобы она не зависела от физических или философских предположений о недетерминированности или вероятности. Грубо говоря, строка является алгоритмической случайной «Мартином-Лёфом» (AR), если она несжимаема в том смысле, что ее алгоритмическая сложность равна ее длине.
AC, AP и AR являются основными субдисциплинами AIT, но AIT проникает во многие другие области. Он служит основой принципа минимальной длины описания (MDL), может упростить доказательства в теории сложности вычислений , используется для определения универсальной метрики сходства между объектами, решает проблему демона Максвелла и многие другие.
{{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )