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

По теореме о рекурсии, программа может знать свой исходный код. Значит, в неё можно написать функцию [math] \mathrm{getSrc()} [/math], которая вернёт строку — исходный код программы. Далее будем считать, что такая функция определена в каждой программе.

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

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

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

[math]\triangleright[/math]

Допустим, что он разрешим. Тогда напишем такую программу: p(x): if u(getSrc(), x) while true else return 1 Если [math] u(p, x) = 1 [/math], тогда программа [math] p [/math] на входе [math] x [/math] должна вернуть [math] 1 [/math], но по условию [math] if [/math] она зависает, а следовательно, не принадлежит универсальному языку. Если же [math] u(p, x) \neq 1 [/math], то мы пойдём во вторую ветку условного оператора и вернём [math] 1 [/math], значит, пара [math] \langle p, x \rangle [/math] принадлежит универсальному языку, но [math] u(p, x) \neq 1 [/math], значит, пара не принадлежит. Опять получили противоречие.

[math]\triangleleft[/math]

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

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

[math] L_A [/math] — множество программ, удовлетворяющих св-ву [math] A [/math].

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

 propA(code):
   // программа, разрешающее свойство языка [math] A [/math]
 f(x):
   // такая программа [math] f [/math], что [math]f \in A [/math]; существует потому что [math] A [/math] — нетривиальное свойство
 g(x):
   // такая программа [math] g [/math], что [math]g \notin A [/math]; существует потому что [math] A [/math] — нетривиальное свойство 
 p(x):
   if propA(getSrc())
       return g(x)
   else
       return f(x)

Если [math] p [/math] не удовлетворяет свойству [math] A [/math], тогда будет выполняться всегда вторая ветка, и [math] L(p) = L(f) [/math]. Но язык программы [math] f [/math] принадлежит [math] A [/math]. Получили противоречие.

Если [math] p [/math] удовлетворяет свойству [math] A [/math], то [math] L(p) = L(g) [/math], а [math] g \notin A [/math]. Опять получили противоречие.

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

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

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

Сложность считается в каком-то фиксированном языке программирования. Так, например, у языков C++ и Python будет разная колмогоровская сложность одной программы.

Пример

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

Busy beaver

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

Функция Busy beaver невычислима.

[math]\triangleright[/math]

Предположим, что это не так. Тогда напишем такую программу p(): for i = 1..BB([math]|\mathrm{getSrc()}|[/math]) + 1 do smth Такая программа всегда совершает больше шагов, чем функция [math] BB [/math] от этой программы. А это невозможно, так [math] BB(|p|) [/math] равна максимальному числу шагов как раз этой программы. Получили противоречие.

[math]\triangleleft[/math]

Аналог I теоремы Гёделя о неполноте

Теорема:

В любой "достаточно богатой системе" существует истинное недоказуемое утверждение.

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

[math]\triangleright[/math]

Поясним, что это значит. Так как любой язык программирования эквивалентен машине Тьюринга, то всё связанное с ним кодируется в логике первого порядка с аксиомами Пеано (для этого достаточно, чтобы программа умела прибавлять к числу единицу и вызывать подпрограммы), поэтому можно в терминах программ получать утверждения, эквивалентные тем, что строил Гёдель. Можно переформулировать теорему следующим образом: невозможно доказать, что [math] p(x) = \perp [/math]. Тогда напишем такую программу: p(x): foreach q [math] \in ~ \Sigma^* [/math] if q proves "p(x) зависает" exit

[math]\triangleleft[/math]

Теорема о неподвижной точке

Зафиксируем главную нумерацию [math] W [/math]. Обозначим за [math] W_n [/math] множество слов, допускаемых программой с номером [math] n [/math].

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

[math] \exists n : W_n = \{n\} [/math]

[math]\triangleright[/math]

Напишем такую программу: p(q): if p.getSrc() == q.getSrc() return 1 else while true Программа [math] p [/math] знает свой код, что то же самое, что и знает свой номер. Как видно из её кода, она допускает только одно число — свой номер.

[math]\triangleleft[/math]

Пример использования

Используя теорему о рекурсии, приведём простое доказательство неразрешимости языка [math]L=\{p|p(\epsilon)=\perp\}[/math].

Лемма:

Язык [math]L=\{p|p(\epsilon)=\perp\}[/math] неразрешим.

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

[math]\triangleright[/math]

Предположим обратное, тогда существует программа [math]r[/math] разрещающая [math]L[/math]. Рассмотрим следущую программу: p(x) if r(p) return 1 while true Пусть [math]p(\epsilon)=\perp[/math]. Тогда условие [math]r(p)[/math] выполняется и [math]p(\epsilon)=1[/math]. Противоречие. Если [math]p(\epsilon) \ne \perp[/math], то [math]r(p)[/math] не выполняется и [math]p(\epsilon)=\perp[/math]. Противоречие.

[math]\triangleleft[/math]

Ссылки

• Wikipedia — Kolmogorov_complexity
• Kolmogorov Complexity
• Дмитрий Ицыксон — Вычислимость и логика, Колмогоровская сложность