141
правка
Изменения
→Теорема Райса-Шапиро: Начало доказательства леммы 2 внутри теоремы Райса-Шапиро
Пусть <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>). Противоречие, так как брали неразрешимое <tex>K</tex>.
}}
Если <tex>A</tex> - перечислимое свойство функций, <tex>g \in A</tex>, то <tex>\exists h</tex>, такое что <tex>|Dom(h)| < +\infty</tex>, <tex>g</tex> - продолжение <tex>h</tex>, <tex>h \in A</tex>.
|proof =
Рассмотрим перечислимое и неразрешимое множество <доказательствоtex>K</tex> и следующую программу: <tex>V(n, x) = \begin{cases} g(x)\text{, if (1);}\\ \perp\text{, else;} \end{cases}</tex> где условие <tex>(1)</tex> следующее: через <tex>x</tex> шагов перечисления <tex>K</tex> число <tex>n</tex> не появилось. <продолжение доказательства леммы>
}}
