Изменения
→Теорема Успенского-Райса
Не умаляя общности, можно считать, что <tex>\varnothing \notin A</tex> (в противном случае перейдём к <tex> \mathrm {RE} \setminus A</tex>, которое также будет разрешимым и нетривиальным, так как <tex> \mathrm {RE} \setminus A \neq \varnothing </tex> и <tex> \mathrm {RE} \setminus A \neq \mathrm {RE} ) </tex>.
Поскольку <tex>A</tex> непусто, то найдётся перечислимый язык <tex>X \in A</tex>. Пусть <tex>p_X</tex> {{---}} полуразрешитель <tex>X</tex>. Введем функцию Рассмотрим вспомогательную программу: <tex> U(i, x)</tex>, <tex> i</tex> {{---}} программа, <tex>x</tex> {{---}} слово. <tex>U(i,x)</tex> '''return''' <tex>i(x)</tex>[[Универсальная функция | универсальная функция]]
Тогда для произвольных <tex>i</tex> и <tex> x </tex> можем написать такую программу.
