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