141
правка
Изменения
→Теорема Райса-Шапиро: Осознал и дописал доказательство леммы 2 внутри теоремы Р-Ш. Многократное спасибо Филиппу за помощь в понимании
Пусть <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>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>\not\exists h</tex>, удоволетворяющая условию леммы.
Рассмотрим перечислимое и неразрешимое множество <tex>K</tex> и следующую программу:
где условие <tex>(1)</tex> следующее: через <tex>x</tex> шагов перечисления <tex>K</tex> число <tex>n</tex> не появилось.
}}
Такие функции перечислимы. Значит такие функции, удоволетворяющие <tex>A</tex>, тоже перечислимы.
<tex>A_{\Gamma} \subset subseteq A</tex> по первой вспомогательной лемме.
<tex>A \subset subseteq A_{\Gamma}</tex> по второй вспомогательной лемме.
Значит <tex>A = A_{\Gamma}</tex>. Теорема доказана.
}}
