Материал из Викиконспекты
Определение образца
| Определение: |
| Пусть [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]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]\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]\triangleleft[/math] |
<продолжение доказательства теоремы>
|
| [math]\triangleleft[/math] |
