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

Неразрешимость универсального языка

Считаем, что язык программ над тем же алфавитом, что и язык входных данных. Если это не так, то можно просто взять объединение алфавитов, это ничто не испортит.

Универсальная программа: [math] u(p, x) = p(x) [/math].

Универсальный язык: [math] L_u = \{ \lt p, x\gt \mid u(p, x) = 1 \} [/math]

Утверждение:

Универсальный язык неразрешим

[math]\triangleright[/math]

Напишем такую программу: p(x): if u(p, x) // можем так написать, потому что по теореме о рекурсии программа может знать свой код return 0 else return 1 Если [math] u(p, x) = 1 [/math], тогда программа [math] p [/math] на входе [math] x [/math] возвращает [math] 1 [/math], но по условию [math] if [/math] она должна вернуть 0, а следовательно, не принадлежит универсальному языку. Если же [math] u(p, x) = 0 [/math], то мы пойдём во вторую ветку условного оператора и вернём [math] 1 [/math], значит, пара [math] \lt p, x\gt [/math] принадлежит универсальному языку, но [math] u(p, x) = 0 [/math], значит, пара не принадлежит. Опять получили противоречие.

[math]\triangleleft[/math]

Теорема Успенского-Райса

[math] A [/math] — разрешимое семейство языков.

[math] L_A [/math] — язык свойства языков. Допустим, что он разрешим. Тогда напишем такую программу

 p(x):
   if p [math] \in ~ L_A [/math]
     return z(x)
   else
     while true

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

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

Колмогоровской сложностью строки [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]