3622
правки
Изменения
набросок док-ва Колмогоровской сложности
}}
=== Пример ===
Колмогоровская сложность программы, выводящей <tex> n </tex> нулей <tex> K(0^n) \leqslant \log{n} + c </tex>. Просто программа, в которой записано <tex> n </tex> нулей. Но можно записать и более короткую программудля больших <tex> n </tex>, например вот такую:
<code>
<tex>p_n</tex>():
'''for''' i = 1..n
print (0)
</code>
|statement=Колмогоровская сложность {{---}} невычислимая функция.
|proof=
<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>.
}}
== Busy beaver ==
