271
правка
Изменения
→Теорема Райса-Шапиро
\end{cases}</tex>
<tex>V</tex> {{- --}} вычислимая (можно параллельно запустить <tex>g(x)</tex> и проверку, принадлежит ли <tex>n</tex> множеству <tex>K</tex> (просто перечисляя это множество); если <tex>g(x)</tex> успешно выполнится, то вернуть её результат).
Пусть <tex>p(x)=V(n, x)</tex>.
<tex>\perp</tex>
Такие функции перечислимы. Значит , такие функции, удоволетворяющие <tex>A</tex>, тоже перечислимы.
<tex>A_{\Gamma} \subseteq A</tex> по первой вспомогательной лемме.
<tex>A \subseteq A_{\Gamma}</tex> по второй вспомогательной лемме.
Значит , <tex>A = A_{\Gamma}</tex>.
}}
