Участник:Shersh/Теорема о рекурсии

Колмогоровская сложность

Определение:

Колмогоровской сложностью строки [math] x [/math] называется функция [math] K(x) [/math], которая равна минимальной длине программы [math] p : p(\varepsilon) = x [/math].

Пример

Колмогоровская сложность программы, выводящей [math] n [/math] нулей [math] K(0^n) \leqslant \log{n} + c [/math]. Просто программа, в которой записано [math] n [/math] нулей. Но можно записать и более короткую программу, например вот такую:

 [math]p_n[/math]():
   for i = 1..n
     print 0

Теорема (Невычислимость Колмогоровской сложности):

Колмогоровская сложность — невычислимая функция.