129
правок
Изменения
Отмена правки 56248 участника AMaltsev (обсуждение)
Пусть <tex>p_\infty</tex> {{---}} всегда зацикливающийся алгоритм. Для упрощения предположим, что <tex>p_\infty \in A</tex>. В противном случае доказательство аналогично.
Рассмотрим <tex>p_a</tex> {{---}} программу, такую что <tex>a \in \overline A</tex> (такое <tex>a</tex> существует, т.к. <tex>А</tex> {{---}} нетривиально). Рассмотрим также произвольное перечислимое неразрешимое множество <tex>X</tex>. Пусть <tex>p_X(n)</tex> {{---}} полуразрешитель <tex>X</tex>.
Зафиксируем произвольное <tex>n \in \mathbb{N}</tex> и построим следующую функцию
<tex>Vn(x) = \begin{cases}
p_a(x), n \in X ; \\ p_\infty(x), n \notin X ; \\
\end{cases} </tex>
