313
правок
Изменения
→Невычислимость
|statement=
<tex>KS(x)</tex> невычислима.
Пусть <tex>KS(x)</tex> вычислима. Возьмем вместо <tex>f(x)\ KS(x)</tex>. Очевидно, что <tex>KS(x) \leqslant KS(x)</tex>, но из принципа несжимаемости ясно, что <tex>KS(x)</tex> неограничена. Противоречие. Следовательно, <tex>KS(x)</tex> невычислима.
<tex> \forall x > x_0: K(x) > f(x)</tex>, если только <tex>f \leqslant const </tex> или <tex> f </tex> {{---}}невычислима.====Альтернативное доказательство====Допустим, что <tex> K </tex> вычислима, тогда напишем такую программу:<code> p(<tex>\varepsilon</tex>): '''foreach''' x <tex>\in ~ \Sigma^* </tex> // перебираем слова по возрастанию длины '''if''' <tex> K(x) > |p|</tex> // теорема о рекурсии используется здесь print(x) exit </code> Начиная с <tex> x_0 </tex>, <tex> f(x) > |p| </tex>.
==Применение==
