141
правка
Изменения
→Теорема Райса-Шапиро: Доказательство самой теоремы
<tex>\Leftarrow</tex>
<tex>\Rightarrow</tex>
|statement =
Пусть <tex>A</tex> - перечислимое свойство функций, <tex>g \in A</tex>, <tex>h</tex> - продолжение <tex>g</tex>.
Если <tex>n \in K</tex>, то <tex>V(n, x) = g(x)</tex> при <tex>x = 0\ldots t-1</tex> для какого-то <tex>t</tex>.
Запустим параллельно проверку, принадлежит ли <tex>n</tex> множеству <tex>K</tex> и проверку, принадлежит ли <tex>V(n, x)</tex> множетсву множеству <tex>A</tex>.
<продолжение доказательства леммы>
Вернёмся к доказательству теоремы. Функции с конечной областью определения записываются так: <tex>f(x):</tex> if <tex>x = x_1</tex> return <tex>y_1</tex> <tex>\cdots</tex> if <tex>x = x_i</tex> return <tex>y_i</tex> <tex>\cdots</tex> <tex>\perp</tex> Такие функции перечислимы. Значит такие функции, удоволетворяющие <tex>A</tex>, тоже перечислимы. <продолжение доказательства теоремыtex>A_{\Gamma} \subset A</tex> по первой вспомогательной лемме. <tex>A \subset A_{\Gamma}</tex>по второй вспомогательной лемме.
Значит <tex>A = A_{\Gamma}</tex>. Теорема доказана.
}}
