Изменения
Нет описания правки
Еще более сильное определение. ''Количество информации'', которое несет строка {{---}} это размер архива, сжатого максимальным образом, самым лучшим архиватором. Но тогда встает вопрос, почему такой архиватор существует. На самом деле он есть, и в некотором смысле '''колмогоровская сложность''' строки {{---}} это размер наименьшей программы, которая печатает эту строку.
==ОпределениеОпределения==
{{Определение
|definition=
|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>.
}}
===Примеры===
* <tex>D(x) = x</tex>, тогда <tex>K_D(x) = |x|</tex>
* <tex>D(x) = xx</tex>, тогда <tex>K_D(0000) = 2, K_D(01) = +\infty </tex>
{{Определение
|definition=
Будем говорить, что декомпрессор <tex>D_1</tex> '''лучше''', чем декомпрессор <tex>D_2</tex>, если <tex>\exists c:\forall x \in \{0, 1\}^*\ K_{D_1}(x) \leqslant K_{D_2}(x) + c</tex>.
}}
