129
правок
Изменения
унификация обозначений
Приведём доказательство от противного. Предположим, что <tex>A</tex> разрешимо.
Рассмотрим язык <tex>p_aS</tex> {{---}} программу, такую такой что <tex>p_a S \in L(\overline {A)}</tex> (такое такой язык существует, так как <tex>p_aA</tex> существует, т.к- нетривиально). Тогда <tex>p_S \in L(\overline{A})</tex> {{---}} нетривиально), а . Рассмотрим также произвольное перечислимое неразрешимое множество <tex>X</tex>. Пусть <tex>p_X(n)</tex> {{---}} полуразрешитель <tex>X</tex>.
Зафиксируем произвольное <tex>n \in \mathbb{N}</tex> и построим следующую функцию
<tex>V_n(x) = \begin{cases}
p_\infty(x), n \notin X \\
\end{cases} </tex>
'''function''' <tex>V_n</tex>(x):
'''if''' <tex>p_X</tex>(n) == 1
'''return''' <tex>p_ap_S</tex>(x)
'''while''' ''true''
</code>
