Теорема Райса-Шапиро — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Мелкая добавка к определению образца)
(Теорема Райса-Шапиро: Начало доказательства леммы 2 внутри теоремы Райса-Шапиро)
Строка 76: Строка 76:
  
 
Пусть <tex>p(x)=V(n, x)</tex>.
 
Пусть <tex>p(x)=V(n, x)</tex>.
Тогда программа, которая запускает параллельно проверку, принадлежит ли <tex>n</tex> множеству <tex>K</tex> (просто перечисляя это множество), и проверку, принадлежит ли <tex>p</tex> множеству <tex>A</tex>, является разрешающей программой для множества <tex>K</tex> (так как если <tex>p \in A</tex>, то <tex>n \notin K</tex> по построению <tex>V(n, x)</tex>). Противоречие.
+
 
 +
Тогда программа, которая запускает параллельно проверку, принадлежит ли <tex>n</tex> множеству <tex>K</tex> (просто перечисляя это множество), и проверку, принадлежит ли <tex>p</tex> множеству <tex>A</tex>, является разрешающей программой для множества <tex>K</tex> (так как если <tex>p \in A</tex>, то <tex>n \notin K</tex> по построению <tex>V(n, x)</tex>).
 +
Противоречие, так как брали неразрешимое <tex>K</tex>.
 
}}
 
}}
  
Строка 84: Строка 86:
 
Если <tex>A</tex> - перечислимое свойство функций, <tex>g \in A</tex>, то <tex>\exists h</tex>, такое что <tex>|Dom(h)| < +\infty</tex>, <tex>g</tex> - продолжение <tex>h</tex>, <tex>h \in A</tex>.
 
Если <tex>A</tex> - перечислимое свойство функций, <tex>g \in A</tex>, то <tex>\exists h</tex>, такое что <tex>|Dom(h)| < +\infty</tex>, <tex>g</tex> - продолжение <tex>h</tex>, <tex>h \in A</tex>.
 
|proof =
 
|proof =
<доказательство>
+
Рассмотрим перечислимое и неразрешимое множество <tex>K</tex> и следующую программу:
 +
 
 +
<tex>V(n, x) =
 +
  \begin{cases}
 +
    g(x)\text{, if (1);}\\
 +
    \perp\text{, else;}
 +
  \end{cases}</tex>
 +
 
 +
где условие <tex>(1)</tex> следующее: через <tex>x</tex> шагов перечисления <tex>K</tex> число <tex>n</tex> не появилось.
 +
 
 +
<продолжение доказательства леммы>
 
}}
 
}}
  

Версия 19:05, 17 января 2012

Определение образца

Определение:
Пусть [math]\gamma=\{\lt x_1,y_1\gt ,\lt x_2,y_2\gt ,...,\lt x_n,y_n\gt \}[/math].
Тогда [math]\gamma[/math] называется образцом.


Свойство образца

Определение:
Пусть [math]A_{\gamma}=\{p | p(x_1)=y_1 \wedge p(x_2)=y_2 \wedge ... \wedge p(x_n)=y_n\}[/math], где [math]\lt x_i, y_i\gt \in \gamma[/math].
Тогда [math]A_{\gamma}[/math] называется свойством образца [math]\gamma[/math].


Лемма о перечислимости свойства образца

Лемма:
Свойство [math]A_{\gamma}[/math] перечислимо для любого образца [math]\gamma[/math].
Доказательство:
[math]\triangleright[/math]

Очевидно, как строится программа, которая возвращает 1, если [math]p \in A_{\gamma}[/math] (запускаем [math]p[/math] на [math]x[/math]-ах и проверяем, что программа вернёт соответствующие [math]y[/math]-ки).

Такой программы достаточно для доказательства перечислимости.
[math]\triangleleft[/math]


Лемма о перечислимости свойства перечислимого множества образцов

Лемма:
Пусть [math]\Gamma[/math] - перечислимое множество образцов, [math]A_{\Gamma} = \bigcup\limits_{\gamma \in \Gamma}{A_{\gamma}}[/math]. Тогда [math]A_{\Gamma}[/math] - перечислимо.
Доказательство:
[math]\triangleright[/math]

Приведём программу, выдающую 1, если [math]p \in A_{\Gamma}[/math]:

[math]q(p):[/math]
  for [math]k = 1..+\infty[/math]
      for [math]\gamma \in \Gamma[1..k][/math]
          if [math](p \in A_{\gamma})|_{TL(k)}[/math]
              return 1
Такой программы достаточно для доказательства перечислимости.
[math]\triangleleft[/math]


Теорема Райса-Шапиро

Теорема:
Свойство функций [math]A[/math] перечислимо тогда и только тогда, когда [math]\exists \Gamma: A = A_{\Gamma}[/math], где [math]\Gamma[/math] - перечислимое множество образцов.
Доказательство:
[math]\triangleright[/math]

[math]\Leftarrow[/math]

Очевидно (перебор по TL).


[math]\Rightarrow[/math]

Здесь нам потребуются две вспомогательные леммы.
Лемма:
Пусть [math]A[/math] - перечислимое свойство функций, [math]g \in A[/math], [math]h[/math] - продолжение [math]g[/math]. Тогда [math]h \in A[/math].
Доказательство:
[math]\triangleright[/math]

Докажем от противного. Пусть [math]g \in A[/math], [math]h[/math] - продолжение [math]g[/math], [math]h \notin A[/math].

Рассмотрим перечислимое и неразрешимое множество [math]K[/math] и следующую программу:

[math]V(n, x) = \begin{cases} h(x)\text{, if $n \in K$;}\\ g(x)\text{, else.} \end{cases}[/math]

[math]V[/math] - вычислимая (можно параллельно запустить [math]g(x)[/math] и проверку, принадлежит ли [math]n[/math] множеству [math]K[/math] (просто перечисляя это множество); если [math]g(x)[/math] успешно выполнится, то вернуть её результат).

Пусть [math]p(x)=V(n, x)[/math].

Тогда программа, которая запускает параллельно проверку, принадлежит ли [math]n[/math] множеству [math]K[/math] (просто перечисляя это множество), и проверку, принадлежит ли [math]p[/math] множеству [math]A[/math], является разрешающей программой для множества [math]K[/math] (так как если [math]p \in A[/math], то [math]n \notin K[/math] по построению [math]V(n, x)[/math]).

Противоречие, так как брали неразрешимое [math]K[/math].
[math]\triangleleft[/math]


Лемма:
Если [math]A[/math] - перечислимое свойство функций, [math]g \in A[/math], то [math]\exists h[/math], такое что [math]|Dom(h)| \lt +\infty[/math], [math]g[/math] - продолжение [math]h[/math], [math]h \in A[/math].
Доказательство:
[math]\triangleright[/math]

Рассмотрим перечислимое и неразрешимое множество [math]K[/math] и следующую программу:

[math]V(n, x) = \begin{cases} g(x)\text{, if (1);}\\ \perp\text{, else;} \end{cases}[/math]

где условие [math](1)[/math] следующее: через [math]x[/math] шагов перечисления [math]K[/math] число [math]n[/math] не появилось.

<продолжение доказательства леммы>
[math]\triangleleft[/math]


<продолжение доказательства теоремы>
[math]\triangleleft[/math]