Изменения

'''return''' <tex>0</tex>

: Построим функцию <tex> a(\varepsilon) </tex>

Число <tex> \alpha </tex> вычислимо <tex>\iff</tex> последовательность знаков представляющей его двоичной записи вычислима.

|proof=

: Если число <tex> \alpha </tex> {{---}} рациональное, то необходимую последовательность можно получить, воспользовавшись стандартным алгоритмом перевода числа в двоичную систему счисления. Рассмотрим случай, когда <tex> \alpha \in \mathbb R \setminus \mathbb Q </tex>.

'''return''' <tex>t</tex>

: Для любого рационального <tex> \varepsilon > 0 </tex>, найдем <tex> n: 2^{-n} < \varepsilon </tex>, тогда в качестве значения функции <tex> a(\varepsilon) </tex> можно взять часть последовательности знаков двоичной записи <tex> \alpha </tex> с <tex> n </tex> знаками после запятой.

}}

Число <tex> \alpha </tex> вычислимо <tex>\iff</tex> существует вычислимая последовательность рациональных чисел, вычислимо сходящаяся к <tex> \alpha </tex>.

|proof=

: Так как <tex> \alpha </tex> вычислимо, то, согласно предыдущей теореме, вычислима и его двоичная запись. Пусть <tex> r_n </tex> {{---}} часть последовательности знаков двоичной записи <tex> \alpha </tex> с <tex> n </tex> знаками после запятой. Данная последовательность вычислима, а также вычислимо сходится к <tex> \alpha </tex>, так как <tex> N(\varepsilon) = \lceil -\log_2 \varepsilon \rceil</tex>.

: Пусть <tex> a(\varepsilon) = r_{N(\varepsilon)} </tex>, тогда <tex> \alpha </tex> вычислимо по определению.

Число <tex> \alpha </tex> перечислимо снизу <tex>\iff</tex> существует вычислимая возрастающая последовательность рациональных чисел, пределом которой является <tex> \alpha </tex>.

|proof=

: По определению <tex> \alpha </tex>, множество <tex> A = \{ a \in \mathbb Q \mid a < \alpha \} </tex> перечислимо. Кроме того, <tex> \sup A = \alpha </tex>.

: По определению нижней грани, <tex> \forall \varepsilon > 0\ \exists x_\varepsilon \in A: \varepsilon > \alpha - x_\varepsilon </tex>. Тогда можно взять, например, последовательность <tex> a_n = x_{\dfrac{1}{n}} </tex>.

: Построим полуразрешитель для множества <tex> A </tex>: