Интересно, можно ли сформулировать теорему, которая бы показывала что с ростом сложности (надо еще понять как строго определить это понятие) системы количество содержательных структур на ней снижается.
Есть такое понятие - колмогоровская сложность. Если мы зафиксируем программу, которая восстанавливает двоичные слова по их описаниям, то сложность слова - это минимальная длина его описания.
(Подробно)
Пусть
– множество всех двоичных слов. Определенный на некотором подмножестве
алгоритм
, преобразующий двоичное слово в другое двоичное слово, назовем декомпрессором. Это название связано с тем, что на практике приходится иметь дело с алгоритмами распаковки файла из архива. Если
,
называется описанием
при данном
. То есть декомпрессор восстанавливает слово по его описанию.
Зафиксируем некоторый декомпрессор
. Рассмотрим какое-нибудь
. Вообще говоря, у него может быть больше одного описания (иначе говоря, прообраза), т.к.
– не обязательно инъекция. У него может и не быть никакого описания, если
не входит в область значения
.
Построим функцию
такую, что:
- если
имеет описания,
равна длине его самого короткого описания
- если
не имеет описаний,
равна
.
Так определенная функция
называется
простой колмогоровской сложностью слова
относительно декомпрессора
.
Скажем, что декомпрессор
не хуже декомпрессора
, если существует такая константа
, что для любого
Далее доказывается, что есть декомпрессор, который не хуже любого другого. Он называется оптимальным декомпрессором. Тривиально, что он перечисляет всё множество двоичных слов, то есть для любого слова
найдётся его описание
, так как оптимальный декомпрессор по определению не хуже тождественного.
Простой колмогоровской сложностью
слова
называют его простую колмогоровскую сложность относительно какого-нибудь оптимального декомпрессора и говорят, что она определена с точностью до аддитивной константы. Как отмечают в своём учебнике Шень и компания
Цитата:
Можно надеяться, что при естественном выборе языков эта константа будет измеряться тысячами или даже сотнями. Тем самым, если мы говорим о сложностях порядка сотен тысяч (скажем, для текста романа) или миллионов (скажем, для ДНК), то уже не так важно, какой именно язык программирования мы выбрали
Например, слово из
сплошных единиц будет иметь очень маленькую сложность, так как его можно описать короткой фразой: "единица, повторённая
раз". Максимальную сложность будут иметь слова, которые невозможно описать иначе, чем просто повторив их побитно. Они "не поддаются сокращению".
Однако такое понимание сложности не исчерпывает нашего интуитивного представления. Если судить по нему, максимально сложным явлением является какой-нибудь воздушный шарик с газом, молекулы которого беспорядочно бьются в стенки. Между тем интуитивно воздушный шарик с газом чрезвычайно прост по сравнению с живой клеткой.
На эту трудность в формализации сложности указывал ещё Пригожин, и насколько я в курсе, с его времени дело не слишком сдвинулось. Впрочем, я ни с какого боку не специалист.