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