Изменения
Нет описания правки
===Тривиальные свойства===
* <tex>KS(x) \leqslant |x| + c</tex>
* <tex>KS(x,y) \leqslant KS(x) + KS(y) + 2\lceil \log_2 KS(x) \rceil + 2</tex>
* Если <tex>A</tex> {{---}} алгоритм, то <tex>KS(A(x)) \leqslant KS(x) + c_A</tex> <br> (<tex>A(x)</tex> запишем как пару {{---}} информация об алгоритме <tex>A</tex> и информация о строке <tex>x</tex>, по предыдущему пункту нам нужно закодировать только сложность первого аргумента, что есть константа)
* '''Принцип несжимаемости:''' <tex>\exists x \in \{0,1\}^n : KS(x) \geqslant n</tex> <br> (Какой бы у нас ни был архиватор, он не может все строки фиксированной длины делать меньше. Строк длины меньшей, чем <tex>n</tex> {{---}} <tex>(2^n-1)</tex>, мы не сможем деархивировать)
|proof=
Пусть <tex>A(n) = \arg\min \limits_{x} f(x) \geqslant n</tex>, где <tex>n \in N</tex>, тогда <tex>A(n)</tex> {{---}} вычислимая (т.к <tex>f(x)</tex> {{---}} вычислима и ограничена), всюду определенная функция. <br>
По свойству невозрастания <tex>KS(x)</tex> при алгоритмических преобразованиях, <tex>KS(A(n)) \leqslant KS(n) + c_1 \leqslant \log_2 n + c_2</tex>. <br> Вспомним, что <tex>f(x) \leqslant KS(x)</tex>, следовательно <tex>KS(A(n)) \geqslant f(A(n)) \geqslant n</tex>. <br> Отсюда: <tex>\forall n : \log_2 n + c_2 \geqslant n</tex>, но ясно, что при больших <tex>n</tex> это неравенство не выполняется. Противоречие.
}}
<hr>
|statement= Простых чисел бесконечно много.
|proof=
Предположим, что простых чисел конечное число. Тогда любое число <tex>n = {p_1}^{\alpha_1}{p_2}^{\alpha_2}\dots{p_k}^{\alpha_k}</tex>, где <tex>k</tex> {{---}} это некоторая константа. Возьмём <tex>n</tex> наибольшей колмогоровской сложности. Тогда <tex>KS(n) \geqslant \log_2 n</tex>, но также <tex>KS(n) \leqslant 2 k \log_2 \log_2 n + c</tex>, т.к. <tex>\alpha_i \leqslant \log_2 n</tex>. Но это неравенство не будет выполняться на достаточно больших <tex>n</tex>, противоречие.
}}
