271
правка
Изменения
→Теорема Райса-Шапиро
Пусть <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</tex> ведёт себя как <tex>h</tex>, которая не содержится в <tex>A</tex>); пусть в этом случае разрешающая программа для <tex>K</tex> возвращает 1;
* если <tex>n \notin K</tex>, то проверка (1) зависнет, а проверка (2) завершится (так как <tex>p</tex> ведёт себя как <tex>g</tex>, которая содержится в <tex>A</tex>); пусть в этом случае разрешающая программа для <tex>K</tex> возвращает 0.
где условие <tex>(0)</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>, потому чтотак как:
* если <tex>n \notin K</tex>, то <tex>V(n, x) \equiv g(x)</tex> для <tex>\forall n</tex>, поэтому проверка (2) завершится. Проверка (1) зависнет. Пусть в этом случае разрешающая программа для <tex>K</tex> возвращает 0;
* если <tex>n \in K</tex>, то завершится проверка (1). Также, в этом случае <tex>|Dom(V(n, x))| < +\infty</tex>, так как <tex>V(n, x) = g(x)</tex> при <tex>x = 0\ldots t-1</tex> для какого-то <tex>t</tex>. <tex>g</tex> является продолжением <tex>V(n, x)</tex>. По предположению от противного <tex>V(n, x) \notin A</tex> <tex>\Rightarrow</tex> проверка (2) зависнет. Пусть в этом случае разрешающая программа для <tex>K</tex> возвращает 1.
