Изменения
→Теорема Райса-Шапиро
Тогда <tex>h \in A</tex>.
|proof =
Докажем от противного.Пусть <доказательствоtex>g \in A</tex>, <tex>h</tex> - продолжение <tex>g</tex>, <tex>h \notin A</tex>. Рассмотрим перечислимое и неразрешимое множество <tex>K</tex> и следующую программу: <tex>V(n, x) = \begin{cases} h(x)\text{, if $n \in K$;}\\ g(x)\text{, else.} \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>n</tex> множеству <tex>K</tex>, и проверку, принадлежит ли <tex>p</tex> множеству <tex>A</tex>, являются разрешающей программой для множества <tex>K</tex>. Противоречие.
}}
