Изменения
Нет описания правки
Можем дать следующее определение. ''Количество информации'', которое несет строка {{---}} это размер архива, полученного сжатием строки каким-то конкретным архиватором (например, LZW). Это более нетривиальная задача, но мы можем придумать строку, которая явно несет в себе мало информации, но которую архиватор тем не менее не сожмет.
Еще более сильное определение. ''Количество информации'', которое несет строка {{---}} это размер архива, сжатого максимальным образом, самым лучшим архиватором. Но тогда встает вопрос, почему такой архиватор существует.На самом деле он есть, и в некотором смысле '''колмогоровская сложность''' строки {{---}} это размер наименьшей программы, которая печатает эту строку. ==Определение=={{Определение|definition=Назовём '''декомпрессором''' <tex>D : \{0, 1\}^* \to\left[\begin{array}{l}\{0, 1\}^* \\\bot\end{array}\right.</tex> алгоритм, восстанавливающий разжатый текст из сжатого.}}Примечание: для простоты мы будем рассматривать бинарный алфавит, но все утверждения мы можем обобщить на строки произвольного алфавита. Относительно каждого декомпрессора мы можем определить понятие сложности строки:{{Определение|definition=Пусть <tex>x \in \{0, 1\}^* </tex>, тогда назовем '''колмогоровской сложностью''' строки <tex>K_D(x) = \min \limits_{y}\ \{|y|\ |\ D(y) = x \}</tex>, размер минимальной строки <tex>y</tex>, такой, что <tex>D(y) = x</tex>. <br> Если такого <tex>y</tex> не существует, тогда <tex>K_D(x) = +\infty</tex>.}}
