Математическая энциклопедия - алгоритмическая теория информации

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

Центральным понятием А. т. и. является понятие энтропии индивидуального объекта, называемое сложностью объекта (по Колмогорову). Интуитивно под этим понимается минимальное количество информации, необходимое для восстановления данного объекта. Точное определение понятия сложности индивидуального объекта и на основе этого понятия количества информации в индивидуальном объекте уотносительно индивидуального объекта хбыло дано А. Н. Колмогоровым в 1962-65, что и послужило началом развития А. т. и.

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

Пусть F(s) - произвольная словарная частично рекурсивная функция. Тогда под сложностью слова хпо Fпонимается:

Слово ртакое, что F(р)=х, наз. кодом, или программой, по к-рой Fвосстанавливает слово х. Имеет место теорема: существует частично рекурсивная функция F0 (называемая оптимальной) такая, что для любой частично рекурсивной функции Fвыполняется неравенство: где CF - константа, не зависящая от х. Эта теорема позволяет дать инвариантное (с точностью до аддитивной константы) определение сложности: сложностью К(х).слова хназ. сложность по нек-рой раз и навсегда фиксированной оптимальной частично рекурсивной функции F0. Очевидно, , где С - константа, не зависящая от х.

Используя К(х), можно определить также сложность K( х, у).пар слов ( х, у):для этого пары ( х, у).эффективно кодируются в виде одного слова с( х, у), и под сложностью К( х, у).понимается К(с( х, у)).

П. Мартином-Лёфом был исследован вопрос о том, как ведет себя сложность начальных кусков бесконечных двоичных последовательностей. Пусть означает начальный кусок последовательностп , составленной из первых пзнаков. Тогда почти все (относительно меры Лебега) бесконечные двоичные последовательности обладают свойствами: а) для бесконечно многих натуральных псправедливо неравенство где с - нек-рая константа; б) для всех натуральных и, больших нек-рого , где произвольное положительное число (теорема Мартина-Лёфа). С другой стороны, для любой последовательности существует бесконечно много натуральных птаких, что <

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

Имеет место теорема: существует частично рекурсивная функция (называемая оптимальной) такая, что для любой другой частично рекурсивной функции Gвыполняется неравенство где константа, не зависящая от х. Сложностью разрешения слова наз. сложность по нек-рой раз и навсегда фиксированной оптимальной частично рекурсивной функции С 0. Очевидно, <: и Используя , можно для любого множества натуральных чисел Мопределить сложность для п-куска множества М:, где характеристическая последовательность множества (=1, если , и ,, если ).

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

Из теоремы Мартина-Лёфа следует существование множеств, для к-рых При этом оказывается, что максимально сложные множества уже существуют среди множеств, задаваемых арифметич. предикатами с двумя кванторами. Однако в случае рекурсивно перечислимых множеств имеет место теорема: а) для любого рекурсивно перечислимого множества Ми любого псправедливо неравенство где не зависит от ; б) существует рекурсивно перечислимое множество Мтакое, что для любого имеет место неравенство В то же время существуют такие рекурсивно перечислимые множества М, что при ограничении времени вычислений произвольной общерекурсивной функцией tимеет место оценка не зависит от .

В указанных терминах можно дать также характеристику универсальных по нек-рому типу сводимости множеств (см. Универсальное множество):множество Мявляется слабо таблично универсальным тогда и только тогда, когда существует неограниченная общерекурсивная функция такая, что для любого имеет место неравенство