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

Материал из Викиконспекты
Перейти к: навигация, поиск
(неразрешимость универсального языка)
(набросок теоремы Успенского-Райса)
Строка 24: Строка 24:
 
}}
 
}}
 
== Теорема Успенского-Райса ==
 
== Теорема Успенского-Райса ==
 +
<tex> A </tex> {{---}} разрешимое семейство языков.
 +
 +
<tex> L_A </tex> {{---}} язык свойства языков. Допустим, что он разрешим. Тогда напишем такую программу
 +
 +
<code>
 +
  p(x):
 +
    '''if''' p <tex> \in ~ L_A </tex>
 +
      '''return''' z(x)
 +
    '''else'''
 +
      '''while''' ''true''
 +
</code>
 
== Колмогоровская сложность ==
 
== Колмогоровская сложность ==
 
{{Определение
 
{{Определение
Строка 48: Строка 59:
 
   p(<tex>\varepsilon</tex>):
 
   p(<tex>\varepsilon</tex>):
 
     '''foreach''' x <tex>\in ~ \Sigma^* </tex> // перебираем слова по возрастанию длины
 
     '''foreach''' x <tex>\in ~ \Sigma^* </tex> // перебираем слова по возрастанию длины
       '''if''' <tex> K(x) > |p|</tex>
+
       '''if''' <tex> K(x) > |p|</tex> // теорема о рекурсии используется здесь
 
         print(x)
 
         print(x)
 
         exit     
 
         exit     

Версия 16:30, 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] 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]

Busy beaver

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

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

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