3622
правки
Изменения
→Пример: колмогоровская сложность
}}
=== Пример ===
Колмогоровская сложность программы, выводящей <tex> n </tex> нулей <tex> K(0^n) \leqslant \log{n} + c </tex>. Просто программа, в которой записано <tex> n </tex> нулей. Но можно записать и более короткую программу для больших <tex> n </tex> со сложностью <tex> K(0^n) \leqslant \log{n} + c </tex>, например вот такую:
<code>
<tex>p_n</tex>():
Начиная с <tex> x_0 </tex>, <tex> f(x) > |p| </tex>.
}}
== Busy beaver ==
== Аналог I теоремы Гёделя о неполноте ==
