271
правка
Изменения
→Теорема Райса-Шапиро
<tex>V(n, x) =
\begin{cases}
g(x)\text{, if (10);}\\
\perp\text{, else;}
\end{cases}</tex>
где условие <tex>(10)</tex> следующее: через <tex>x</tex> шагов перечисления <tex>K</tex> число <tex>n</tex> не появилось.
Тогда программа, которая запускает параллельно проверку (1), принадлежит ли <tex>n</tex> множеству <tex>K</tex> (просто перечисляя это множество) и проверку (2), принадлежит ли <tex>V(n, x)</tex> множеству <tex>A</tex>, является разрешающей программой для множества <tex>K</tex>, потому что:
