3622
правки
Изменения
м
→Теорема Успенского-Райса
Приведём доказательство от противного. Предположим, что <tex>A</tex> разрешимо.
Рассмотрим язык <tex>S</tex>, такой что <tex> S \in \overline{A}</tex> (такой язык существует, так как <tex>A</tex> {{- --}} нетривиально). Тогда <tex>p_S \in L(\overline{A})</tex>.
Рассмотрим также произвольное перечислимое неразрешимое множество <tex>X</tex>. Пусть <tex>p_X(n)</tex> {{---}} полуразрешитель <tex>X</tex>.
