Алгоритмические варианты понятия энтропии

В 1965 году А. Н. Колмогоров ввел понятие сложности, или энтропии35) конечного объекта (см. [8]). Говоря неформально, энтропия объекта есть количество двоичных знаков, необходимых для описания (задания, определения) этого объекта. Разумеется, это количество зависит от выбора ! способа описаниятаким образом, каждому способу описания соответствует своя функция сложности. Открытие Колмогорова как раз и состояло в том, что при естественном определении понятия «способ описания» среди всех таких способов существует оптимальный — такой, при котором сложность объектов меньше, чем при любом другом (с точностью до ограниченного слагаемого). Если имеются два разных оптимальных способа описания, то соответствующие им сложности отличаются, очевидно, на ограниченное слагаемое. Таким образом, возможно дать не зависящее от выбора способа описания оцреде-ление энтропии конечного объекта как его сложности при оптимальном способе описания. Введенную Колмогоровым энтропию мы будем называть простой колмогоровской энтропией.

Позднее были предложены другие варианты понятия энтропии конечного объекта — сложность (энтропия) разрешения (см. [sJ), префиксная энтропия, монотонная энтропия (о двух последних см.). Хотя эти понятия основаны на родственных идеях — все они тем или иным способом уточняют описанный выше замысел Колмогорова, — их формальные определения никак не были связаны друг с другом. Ниже предлагается некоторая общая схема, частх) Мы предпочитаем термин «энтропия», чтобы избежать смешения со «сложностями вычисления» (временной, емкостной и т. п.)ными случаями которой являются все перечисленные (а также некоторые другие) варианты определения понятия энтропии конечного объекта.

Эта схема использует понятиепространства в смысле Ю. Л. Ершова [4]. Понятиепространства является чрезвычайно удобным средством для определения вычислимости отображений, область определения которых состоит из объектов более сложной природы, чем натуральные числа (функций, последовательностей и т. д.). Поясним это понятие на следующем важном примере.

Пусть мы имеем отображение <71 область определения которого состоит из (частичных) функций из jff в /|У. Пусть это отображение в каком-то смысле вычислимо. Естественно считать, что к любому моменту процесса вычисления значенияQL на функции ^ используется не вся информация о ^ (ибо как может алгоритмический процесс успеть использовать бесконечно много информации об ?!), а лишь конечное число равенств вида — ё. Другими словами, значение отображения 01 на функции? определяется значениями этого отображения на конечных частях. Ясно также, что по мере увеличения использованной информации об будет получаться все больше и больше информации о результате применения 01 к? (если этот результат также является функцией, то будут становиться известными ее значения во все большем числе точек).

Другая важная идея, которую использует описываемая схема определения энтропии — идея интерпретации операций логики высказываний (конъюнкции, дтзъюнкции, импликации) как операций не над утверждениями, а над задачами. Эта идея была предложена А. Н. Колмогоровым в [/2J и уточнена впоследствии Ю. Т. Медведевым в [з]. Говоря неформально, задача определяется двумя множествами — множеством X «возможных решений» задачи и его подмножеством, А — подмножеством «действительно решений». Например, задачу «перечислить все элементы множества QcfM «можно рассматривать как пару таких множеств: множеством возможных решений считается множество, всех последовательностей натуральных чисел, а действительными решениями считаются те последовательности h i—* t душ которых IN} =Q. Можно сказать, что задача есть задача «отыскания среди элементов X элемента, принадлежащего Д «.

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

В работе исследуются свойства описанной схемы. Устанавливается ее связь с интуиционистской логикой высказываний. С точки зрения этой схемы исследуется также понятие априорной вероятности. Дадим теперь более подробный обзор содержания работы.

1. Агафонов В. Н. Сложность алгоритмов и вычислений. Спецкурс для студентов НГУ, часть 2. Новосибирск: Изд-во НГУ, 1975. 146 с.

2. Вьюгрш В. В. Алгоритмическая энтропия (сложность) конечных объектов и ее применение к определению случайности и количества информации. -Семиотика и информатика. М.:ВИНИТИ, 1980, вып. 16, с. 14−43.

3. Драгалин А. Г. Математический интуиционизм.

Введение

в теорию доказательств. М.:Наука, 1979. 256 с.

4. Ершов Ю. Л. Вычислимые функционалы конечных типов. -Алгебра и логика, 1972, т. II, Л 4,'с. 367 437.

5. Звонкин А. К., Левин Л. А. Сложность конечных объектов и обоснование понятий информации и случайности с помощью теории алгоритмов. Успехи матем. наук, 1970, т. 25, вып. 6 (156), с. 85 — 127.

6. Кпини С. К.

Введение

в метаматематику. Пер. с англ. М.: Изд-во иностр. лит., 1957. 526 с.

7. Колмогоров А. Н. Три подхода к определению понятия «количество информации». Проблемы передачи информации, 1965, т. I, вып. I, с. 3 — II.

8. Колмогоров А. Н. К логическим основам теории информации’л теории вероятностей. Проблемы передачи информации, 1969, т. 5, вып. 3, с. 3 — 7.

9. Медведев Ю. Т. Финитные задачи. Докл. АН, 1962, т. 142, й 5, с. 1015 — 1018. 13о.

10. Новиков П. О. Конструктивная математичеекая логика с точки зрения классической. М.:Наука, 1977. 328 с.

11. Роджерс X. Теория рекурсивных функций и эффективная вычислимость. Пер. с англ. М.:Мир, 1972. 624 с.

12. Успенский В. Л., Семенов А. Л. Теория алгоритмов: ее основные открытия и приложения. В кн.: Алгоритмы в современной математике и ее приложениях. Часть I. / А. П. Ершов, Д. Кнут, редакторы. Новосибирск: Вычислительный центр СО АН СССР, 1982, с. 99−342.

13. Шень А. Х. Исчисление задач ипространства. В кн.: У1 Всесоюзная конференция по математической логике. Тбилиси, 30. XI — 2.ХП.1982 г. Тезисы докладов. Тбилиси: Изд-во Тбилисского университета, 1982, с. 204.

14. Шень А. Х. Понятие (, р)-стохастичности по Колмогоровуи его свойства. Доклады АН, 1983, т. 271, 1Ь 6, а 1337 — 1340.

15. Шень А. Х. Алгоритмические варианты понятия энтропии. Доклады АН, 1984, т. 276, J3 3, с. 563 — 566 .

16. Р. Он Ш гчШ1ол d^criptlo^iconrttxity a. U at^oritk^ic pro&eitity. ~ Пе, огг6исл? Copier ScUfiCz, ШЪ, v. 22, p.n. kotmojoro+f А. Ълг 3>e*tuy oter c*luitL0*Lsti*cUniojik. /Ч^Асис^с/е Zetiscbnf-t, 1931, Bel. ZS, «S. 5» 8 — 65.

17. Hole G. ZProposition^ ё andrtbtLicilt’dy. -Tra^. A^er. tAaU. Sot., 195 3, ' •lo. Schorr C.P. /u^-i^*.- In for-motion Pro ceding, t Proceeding of If7 IP COnyrm ?± (L^etjexna-, , 13?±), V- 1P- 5 С.

18. ScUorr C.P. Optimal Слкт&гЖоль clJopt'*-***GoJlii nuwfrrCy*. ~ MaU^cdUaZ Sjste.1"* Ueoy, 137. S, v. %, ^ 2, p- -/82 — 132.