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

Раздел математич. логики, уточняющий и изучающий на базе понятий алгоритма и вычислимой функции основные понятия теории информации. А. т. и. стремится обосновать эти понятия без помощи обращения к теории вероятностей и так, чтобы понятия энтропии и количества информации были применимы к индивидуальным объектам. Наряду с этим она порождает и свои собственные проблемы, связанные с изучением энтропии конкретных индивидуальных объектов. Центральным понятием А. т. и. является понятие энтропии индивидуального объекта, называемое сложностью объекта (по Колмогорову). Интуитивно под этим понимается минимальное количество информации, необходимое для восстановления данного объекта. Точное определение понятия сложности индивидуального объекта и на основе этого понятия количества информации в индивидуальном объекте уотносительно индивидуального объекта хбыло дано А. Н. Колмогоровым в 1962-65, что и послужило началом развития А. т. и. Без существенных ограничений общности можно рассматривать только двоичные слова (что в дальнейшем и будет делаться). Под сложностью еловая понимается длина l(р).самого короткого (двоичного) слова р, содержащего всю информацию, необходимую для восстановления хпри помощи к.-л. фиксированного способа декодирования. Точное определение этого понятия следующее. Пусть F(s) — произвольная словарная частично рекурсивная функция. Тогда под сложностью слова хпо Fпонимается: Слово ртакое, что F(р)=х, наз. кодом, или программой, по к-рой Fвосстанавливает слово х. Имеет место теорема: существует частично рекурсивная функция F0 (называемая оптимальной) такая, что для любой частично рекурсивной функции Fвыполняется неравенство: где CF — константа, не зависящая от х. Эта теорема позволяет дать инвариантное (с точностью до аддитивной константы) определение сложности: сложностью К(х).слова хназ. сложность по нек-рой раз и навсегда фиксированной оптимальной частично рекурсивной функции F0. Очевидно, , где С — константа, не зависящая от х. Используя К(х), можно определить также сложность K( х, у).пар слов ( х, у):для этого пары ( х, у).эффективно кодируются в виде одного слова с( х, у), и под сложностью К( х, у).понимается К(с( х, у)). П. Мартином-Лёфом был исследован вопрос о том, как ведет себя сложность начальных кусков бесконечных двоичных последовательностей. Пусть означает начальный кусок последовательностп , составленной из первых пзнаков. Тогда почти все (относительно меры Лебега) бесконечные двоичные последовательности обладают свойствами: а) для бесконечно многих натуральных псправедливо неравенство где с — нек-рая константа; б) для всех натуральных и, больших нек-рого , где — произвольное положительное число (теорема Мартина-Лёфа). С другой стороны, для любой последовательности существует бесконечно много натуральных птаких, что < Понятие сложности используется также при изучении алгоритмич. проблем. Здесь более естественной является так наз. сложность разрешения слова х. Интуитивно под этим понимается минимальное количество информации, к-рую надо иметь, чтобы по каждому числу найти г-й знак слова (длину снова хпри этом можно и не знать). Точнее, под сложностью разрешения слова по частично рекурсивной функции понимается Имеет место теорема: существует частично рекурсивная функция (называемая оптимальной) такая, что для любой другой частично рекурсивной функции Gвыполняется неравенство где — константа, не зависящая от х. Сложностью разрешения слова наз. сложность по нек-рой раз и навсегда фиксированной оптимальной частично рекурсивной функции С 0. Очевидно, <: и Используя , можно для любого множества натуральных чисел Мопределить сложность для п-куска множества М:, где — характеристическая последовательность множества (=1, если , и ,, если ). Алгоритмич. проблемы обычно могут быть представлены в виде проблемы вхождения в нек-рое рекурсивно перечислимое множество М. Если мы фиксируем некрое пи ограничиваемся рассмотрением проблемы вхождения в Мтолько для первых пнатуральных чисел, то мы получаем ограниченную алгоритмическую проблему. Величина интуитивно выражает количество информации, к-рую надо иметь, чтобы можно было решить данную ограниченную проблему. В частности, множество Мрекурсивно тогда и только тогда, когда ограничено сверху нек-рой константой. Из теоремы Мартина-Лёфа следует существование множеств, для к-рых При этом оказывается, что максимально сложные множества уже существуют среди множеств, задаваемых арифметич. предикатами с двумя кванторами. Однако в случае рекурсивно перечислимых множеств имеет место теорема: а) для любого рекурсивно перечислимого множества Ми любого псправедливо неравенство где не зависит от ; б) существует рекурсивно перечислимое множество Мтакое, что для любого имеет место неравенство В то же время существуют такие рекурсивно перечислимые множества М, что при ограничении времени вычислений произвольной общерекурсивной функцией tимеет место оценка не зависит от . В указанных терминах можно дать также характеристику универсальных по нек-рому типу сводимости множеств (см. Универсальное множество):множество Мявляется слабо таблично универсальным тогда и только тогда, когда существует неограниченная общерекурсивная функция такая, что для любого имеет место неравенство При изучении сложности ограниченных алгоритмич. проблем иногда используются и другие меры сложности, как, напр., минимальная длина изображения нормального алгорифма, решающего данную ограниченную проблему. Но оказывается, что между введенными выше сложностями и аналогами этих сложностей, выраженными через минимальную длину изображения нормального алгорифма (или через минимальное число внутренних состояний машины Тьюринга), существуют асимптотически точные соотношения (см. Алгоритма сложность). При построении А. т. и. вводится еще понятие у с-ловной сложности слова хпри известном упо частично рекурсивной функции : Для этого понятия также имеет место теорема о существовании оптимальной функции , и условная сложность слова хпри известном уопределяется как сложность по век-рой раз и навсегда фиксированной оптимальной функции интуитивно обозначает минимальное количество информации, к-рое необходимо добавить к информации, содержащейся в слове у, чтобы можно было восстановить слово х. Очевидно,. Следующим центральным понятием А. т. и. является понятие количества информации в индивидуальном объекте y относительно индивидуального объекта х: Величину наз. алгоритмическим количеством информации в об Соответственно величины наз. иногда а л-горит ми ческой энтропией хи алгоритмической условной энтропией хпри заданном . Формулы разложения энтропии и коммутативности информации верны в алгоритмич. концепции лишь с точностью до членов порядка O(logH(X,Y): Между алгоритмич. и классич. определениями количества информации (точнее, между сложностью слова по Колмогорову и энтропией распределения частот по Шеннону) существует определенная связь (А. Н. Колмогоров): пусть задано число rи пусть слово хдлины состоит из слов длины г, причем k-e слово длины rвходит в хс частотой , тогда где и при . В общем случае более тесную связь между энтропией и сложностью установить нельзя. Это объясняется тем, что энтропия приспособлена для изучения текстов, не имеющих других закономерностей, кроме частотных. Следовательно, для случайных последовательностей по мере, соответствующей независимым испытаниям, между рассматриваемыми величинами можно установить полную связь; Аналогичный факт имеет место и для произвольного эргодического стационарного случайного процесса. Лит.:[1] Колмогоров А. Н., "Проблемы передачи информации", 1965, т. 1, вып. 1, с. 3-11; [2] его же, "Проблемы передачи информации", 1969, т. 5, вып. 3, с. 3-7; [3] Звонкий А. К., Левин Л. А., "Успехи матем. наук", 1970, т. 25, вып. 6, с. 85-127; [4] Барздинь Я. М., "Докл. АН СССР", 1968, т. 182, № 6, с. 1249-1252; [5] Канович М. И., "Докл. АН СССР", 1970, т. 194, № 3, с. 500-503. Я. М. Барздинь.