Материал из Викиконспекты
|
|
| Строка 3: |
Строка 3: |
| | {{Определение | | {{Определение |
| | |definition= | | |definition= |
| − | Пусть <tex>\gamma=\{<x_1,y_1>,<x_2,y_2>,...,<x_n,y_n>\}</tex>. | + | Пусть <tex>\gamma=\{<x_1,y_1>,<x_2,y_2>,...,<x_n,y_n>\}</tex>.<br /> |
| | Тогда <tex>\gamma</tex> называется образцом. | | Тогда <tex>\gamma</tex> называется образцом. |
| | }} | | }} |
| Строка 11: |
Строка 11: |
| | {{Определение | | {{Определение |
| | |definition= | | |definition= |
| − | Пусть <tex>A_{\gamma}=\{p | p(x_1)=y_1 \wedge p(x_2)=y_2 \wedge ... \wedge p(x_n)=y_n\}</tex>. | + | Пусть <tex>A_{\gamma}=\{p | p(x_1)=y_1 \wedge p(x_2)=y_2 \wedge ... \wedge p(x_n)=y_n\}</tex>, где <tex><x_i, y_i> \in \gamma</tex>.<br /> |
| | Тогда <tex>A_{\gamma}</tex> называется свойством образца <tex>\gamma</tex>. | | Тогда <tex>A_{\gamma}</tex> называется свойством образца <tex>\gamma</tex>. |
| | }} | | }} |
| Строка 39: |
Строка 39: |
| | if <tex>(p \in A_{\gamma})|_{TL(k)}</tex> | | if <tex>(p \in A_{\gamma})|_{TL(k)}</tex> |
| | return 1 | | return 1 |
| − | Этого достаточно для доказательства перечислимости.
| + | Такой программы достаточно для доказательства перечислимости. |
| | }} | | }} |
| | | | |
Версия 18:58, 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]\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] |
