Изменения

Пусть <tex>p_\infty</tex> {{---}} всегда зацикливающийся алгоритм. Для упрощения предположим, что <tex>p_\infty \in A</tex>. В противном случае доказательство аналогично.

'''Рассмотрим случай, когда <tex>p_\infty \in A</tex>.'''  Рассмотрим <tex>p_a</tex> {{---}} программу, такую что <tex>a \in \overline A</tex> (такое <tex>a</tex> существует, т.к. <tex>A</tex> {{---}} нетривиально). Рассмотрим , а также произвольное перечислимое неразрешимое множество <tex>X</tex>. Пусть <tex>p_X(n)</tex> {{---}} полуразрешитель <tex>X</tex>.

<tex>VnV_n(x) = \begin{cases}

Получили, что если <tex>n \in X</tex>, то <tex>V_n \in L(\overline S)</tex>, а если <tex>n \notin X</tex>, то <tex>V_n \in L(SA)</tex>. Таким образом, <tex>n \in X \iff V_n \in L(\overline SA)</tex>.  Так как <tex>\overline A</tex> {{---}} разрешимо, то можно проверить для любого <tex>a</tex>, лежит ли оно в <tex>\overline{A}</tex>. Но это тоже самое, что и проверка <tex>n \in X</tex>. Тогда можно для каждого <tex>n</tex> проверить, лежит ли оно в <tex>X</tex>, а следовательно и построить разрешитель для <tex>X</tex>. Так как <tex>X</tex> {{---}} неразрешимо, получили противоречие. '''Теперь рассмотрим случай, когда <tex>p_\infty \in \overline{A}</tex>.'''

Так как <tex>\overline S{A}</tex> {{---}} разрешимонетривиально (как дополнение к нетривиальному множеству), то можно проверить для любого <tex>a</tex>, лежит ли по первой части доказательства оно в <tex>\overline{S}</tex>неразрешимо. Но это тоже самоеСледовательно, что и проверка <tex>n \in X</tex>. Тогда можно для каждого <tex>nA</tex> проверить, лежит ли оно в <tex>X</tex>, а следовательно и построить разрешитель для <tex>X</tex>. Так как <tex>X</tex> {{---}} также неразрешимо, получили противоречие.