141
правка
Изменения
→Теорема Райса-Шапиро: Теперь сам понял доказательство первой леммы и поясняю его
Пусть <tex>p(x)=V(n, x)</tex>.
Тогда программа, которая запускает параллельно проверку, принадлежит ли <tex>n</tex> множеству <tex>K</tex>(просто перечисляя это множество), и проверку, принадлежит ли <tex>p</tex> множеству <tex>A</tex>, являются является разрешающей программой для множества <tex>K</tex>(так как если <tex>p \in A</tex>, то <tex>n \notin K</tex> по построению <tex>V(n, x)</tex>). Противоречие.
}}
