Участник: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] n [/math], например вот такую:

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

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

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

Доказательство:

[math]\triangleright[/math]

[math] \forall x \gt x_0: K(x) \gt f(x)[/math], если только [math]f \leqslant const [/math] или [math] f [/math] — невычислима. Допустим, что [math] K [/math] вычислима, тогда напишем такую программу: p([math]\varepsilon[/math]): foreach x [math]\in ~ \Sigma^* [/math] // перебираем слова по возрастанию длины if [math] K(x) \gt |p|[/math] print(x) exit Начиная с [math] x_0 [/math], [math] f(x) \gt |p| [/math].

[math]\triangleleft[/math]