Кафедра ИУ3
22 декабря 2015, 14:00

Верхняя и нижняя оценки Колмогоровской сложности

Докладчик: Выхованец Валерий Святославович

Организация: МГТУ им. Н. Э. Баумана, Интситут проблем управления РАН

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