Колмогоровская сложность: как измерить, насколько сложен текст?
«Колмогоровская сложность» — она же «теория сложности Колмогорова» или «алгоритмическая теория информации».
Представьте, что вам нужно передать другу длинное сообщение. У вас есть два способа.
Способ первый: продиктовать каждую букву отдельно. Это долго и неумно.
Способ второй: найти в сообщении закономерность и сказать короткую инструкцию. Например: "Напиши слово "мама" 500 раз подряд". Это быстро и просто.
Колмогоровская сложность это математическая мера, которая отвечает на вопрос: какая самая короткая инструкция (программа), способная точно описать или сгенерировать данный объект? Чем короче инструкция, тем меньше сложность. Чем длиннее тем выше.
Простые примеры для понимания
Пример 1. Очень простая строка:
AAAAAA...AA (1000 букв А)
Самая короткая инструкция: "напечатай А 1000 раз". Эта инструкция занимает десяток символов. Колмогоровская сложность низкая.
Пример 2. Узор с правилом:
АБАБАБАБ...АБ (1000 символов)
Инструкция: "печатай АБ 500 раз". Тоже коротко. Сложность низкая.
Пример 3. Осмысленная фраза на русском:
Вороне где-то бог послал кусочек сыру
У этой фразы есть внутренние правила (грамматика, лексика, даже отсылка к басне). Её можно сжать, сказав: "первая строка басни Крылова "Ворона и Лисица"". Инструкция очень короткая, а фраза длинная. Значит, настоящая сложность фразы низкая, потому что она опирается на уже существующие закономерности.
Пример 4. Случайная строка:
К д л п р н а с в а ы в п а м и ы в п (бессмысленный набор букв)
В ней нет никаких повторений, нет ритма, нет отсылок к известным текстам. Единственная возможная инструкция: "напечатай следующие буквы в точном порядке: К, пробел, д, л..." и так далее до конца. Эта инструкция будет такой же длинной, как и сама строка. Колмогоровская сложность высокая (максимальная).
Почему это важно?
Колмогоровская сложность предлагает очень чёткую границу между закономерностью и случайностью:
- Закономерность это когда короткое правило порождает длинный объект (стихи, музыка, программа, фрактал).
- Случайность это когда у объекта нет короткого правила. Его можно только перечислить целиком.
Любой осмысленный текст, который мы создаём в культуре: книга, симфония, чертёж здания — обладает низкой колмогоровской сложностью по отношению к своему объёму, потому что он подчиняется правилам (языка, гармонии, логики). Полностью случайный набор символов сжать невозможно.
Самый удивительный факт
Оказывается, не существует универсального способа вычислить колмогоровскую сложность любого текста. Вы не можете написать программу, которая взяла бы любой файл и сказала: «его сложность равна N». Это математически доказано (теорема о невычислимости колмогоровской сложности).
Что это означает на практике?
Всегда остаётся принципиальная возможность: то, что сегодня кажется случайным шумом, завтра может оказаться проявлением глубокой закономерности, которую вы просто не заметили. Другими словами, полное «объяснение» мира упирается в фундаментальный предел нашего познания: мы не можем быть уверены, что нашли самую короткую инструкцию для всего, что нас окружает.
Обновление
После написания нашел намного более подробную и более интересную статью, объясняющую Колмогоровскую сложность.
