3622
правки
Изменения
начата Колмогоровская сложность
== Неразрешимость универсального языка ==
== Теорема Успенского-Райса ==
== Колмогоровская сложность ==
{{Определение
|id=defK.
|definition='''Колмогоровской сложностью''' строки <tex> x </tex> называется функция <tex> K(x) </tex>, которая равна минимальной длине программы <tex> p : p(\varepsilon) = x </tex>.
}}
=== Пример ===
Колмогоровская сложность программы, выводящей <tex> n </tex> нулей <tex> K(0^n) \leqslant \log{n} + c </tex>. Просто программа, в которой записано <tex> n </tex> нулей. Но можно записать и более короткую программу, например вот такую:
<code>
<tex>p_n</tex>():
'''for''' i = 1..n
print 0
</code>
{{Теорема
|id=thK.
|about=Невычислимость Колмогоровской сложности
|statement=Колмогоровская сложность {{---}} невычислимая функция.
|proof=
}}
== Busy beaver ==
== Аналог I теоремы Гёделя о неполноте ==
== Аналог II теоремы Гёделя о неполноте ==
== Теорема о неподвижной точке ==
