Участник:Shersh/Теорема о рекурсии — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(набросок док-ва Колмогоровской сложности)
(неразрешимость универсального языка)
Строка 1: Строка 1:
 
== Неразрешимость универсального языка ==
 
== Неразрешимость универсального языка ==
 +
Считаем, что язык программ над тем же алфавитом, что и язык входных данных. Если это не так, то можно просто взять объединение алфавитов, это ничто не испортит.
 +
 +
Универсальная программа: <tex> u(p, x) = p(x) </tex>.
 +
 +
Универсальный язык: <tex> L_u = \{ <p, x> \mid u(p, x) = 1 \} </tex>
 +
 +
{{Утверждение
 +
|id=proposalU.
 +
|statement=Универсальный язык неразрешим
 +
|proof=
 +
Напишем такую программу:
 +
<code>
 +
  p(x):
 +
    '''if''' u(p, x) // можем так написать, потому что по теореме о рекурсии программа может знать свой код
 +
      '''return''' 0
 +
    '''else'''
 +
      '''return''' 1
 +
</code>
 +
 +
Если <tex> u(p, x) = 1 </tex>, тогда программа <tex> p </tex> на входе <tex> x </tex> возвращает <tex> 1 </tex>, но по условию <tex> if </tex> она должна вернуть 0, а следовательно, не принадлежит универсальному языку.
 +
 +
Если же <tex> u(p, x) = 0 </tex>, то мы пойдём во вторую ветку условного оператора и вернём <tex> 1 </tex>, значит, пара <tex> <p, x> </tex> принадлежит универсальному языку, но <tex> u(p, x) = 0 </tex>, значит, пара не принадлежит. Опять получили противоречие.
 +
}}
 
== Теорема Успенского-Райса ==
 
== Теорема Успенского-Райса ==
 
== Колмогоровская сложность ==
 
== Колмогоровская сложность ==

Версия 16:25, 28 декабря 2013

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

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

Универсальная программа: [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] 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]

Busy beaver

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

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

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