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

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

Определение:

Пусть $\gamma=\{\lt x_1,y_1\gt ,\lt x_2,y_2\gt ,\ldots ,\lt x_n,y_n\gt \}$. Тогда $\gamma$ называется образцом.

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

Определение:

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

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

Лемма:

Свойство $A_{\gamma}$ перечислимо для любого образца $\gamma$.

Доказательство:

$\triangleright$

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

$\triangleleft$

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

Лемма:

Пусть $\Gamma$ - перечислимое множество образцов, $A_{\Gamma} = \bigcup\limits_{\gamma \in \Gamma}{A_{\gamma}}$. Тогда $A_{\Gamma}$ - перечислимо.

Доказательство:

$\triangleright$

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

$\triangleleft$

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

Теорема:

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

Доказательство:

$\triangleright$

$\Leftarrow$ Очевидно (перебор по TL). $\Rightarrow$ Здесь нам потребуются две вспомогательные леммы. Лемма: Пусть $A$ - перечислимое свойство функций, $g \in A$, $h$ - продолжение $g$. Тогда $h \in A$. Доказательство: $\triangleright$ Докажем от противного. Пусть $g \in A$, $h$ - продолжение $g$, $h \notin A$. Рассмотрим перечислимое и неразрешимое множество $K$ и следующую программу: $V(n, x) = \begin{cases} h(x)\text{, if $n \in K$;}\\ g(x)\text{, else.} \end{cases}$ $V$ - вычислимая (можно параллельно запустить $g(x)$ и проверку, принадлежит ли $n$ множеству $K$ (просто перечисляя это множество); если $g(x)$ успешно выполнится, то вернуть её результат). Пусть $p(x)=V(n, x)$. Тогда программа, которая запускает параллельно проверку, принадлежит ли $n$ множеству $K$ (просто перечисляя это множество), и проверку, принадлежит ли $p$ множеству $A$, является разрешающей программой для множества $K$ (так как если $p \in A$, то $n \notin K$ по построению $V(n, x)$). Противоречие, так как брали неразрешимое $K$. $\triangleleft$ Лемма: Если $A$ - перечислимое свойство функций, $g \in A$, то $\exists h$, такое что $|Dom(h)| \lt +\infty$, $g$ - продолжение $h$, $h \in A$. Доказательство: $\triangleright$ Рассмотрим перечислимое и неразрешимое множество $K$ и следующую программу: $V(n, x) = \begin{cases} g(x)\text{, if (1);}\\ \perp\text{, else;} \end{cases}$ где условие $(1)$ следующее: через $x$ шагов перечисления $K$ число $n$ не появилось. Если $n \notin K$, то $V(n, x) = g(x)$. Если $n \in K$, то $V(n, x) = g(x)$ при $x = 0\ldots t-1$ для какого-то $t$. Запустим параллельно проверку, принадлежит ли $n$ множеству $K$ и проверку, принадлежит ли $V(n, x)$ множеству $A$. <продолжение доказательства леммы> $\triangleleft$ Вернёмся к доказательству теоремы. Функции с конечной областью определения записываются так: $f(x):$ if $x = x_1$ return $y_1$ $\cdots$ if $x = x_n$ return $y_n$ $\perp$ Такие функции перечислимы. Значит такие функции, удоволетворяющие $A$, тоже перечислимы. $A_{\Gamma} \subset A$ по первой вспомогательной лемме. $A \subset A_{\Gamma}$ по второй вспомогательной лемме. Значит $A = A_{\Gamma}$. Теорема доказана.

$\triangleleft$