Колмогоровская сложность
Материал из Википедии — свободной энциклопедии
В алгоритмической теории информации колмогоровская сложность объекта (такого, как текст) есть мера вычислительных ресурсов, необходимых для точного определения этого объекта.
Колмогоровская сложность также известна как описательная сложность, сложность Колмогорова — Хайтина, стохастическая сложность, алгоритмическая энтропия или алгоритмическая сложность.
Выражает возможность фрактального описания.
К примеру, рассмотрим две строки длиной 64 символа, содержащие только символы в нижнем регистре и цифры:
abababababababababababababababababababababababababababababababab 4c1j5b2p0cv4w1x8rx2y39umgw5q85s7uraqbjfdppa0q7nieieqe9noc4cvafzf
Первая строка имеет простое описание на естественном языке, а именно ab 32 раза, состоящее из 10 символов. Вторая строка не имеет очевидного простого описания с использованием того же набора символов, кроме собственно самой этой строки, длина которой составляет 64 символа.
Более формально, сложность строки — это длина описания этой строки на некотором универсальном языке описания. Способность сложности к изменению относительно выбора языка описания обсуждается ниже. Колмогоровская сложность любой строки не может быть более, чем на несколько байт больше, чем длина самой этой строки, так как программа может выглядеть как одна команда "напечатать строку", где строка указана в явном виде. Строки, чья колмогоровская сложность слабо зависит от размера самой строки, не считаются сложными.