129
правок
Изменения
м
правки форматирования
<tex> \Longrightarrow </tex>:
: Если <tex> \alpha </tex> {{---}} рациональное, то существует тривиальный разрешитель для <tex> A </tex>, который просто сравнивает полученный элемент с <tex> \alpha </tex>.
: В противном случае, построим разрешитель для <tex> A </tex>:
'''fun'''<tex> p(x)</tex>:
<tex> \Longleftarrow </tex>:
: Построим функцию <tex> a(\varepsilon) </tex>:
'''fun''' <tex> a(\varepsilon) </tex>:
'''return''' x
: Так как <tex> A </tex> разрешимо, <tex> \alpha = \sup A </tex> и для любого <tex> x \in A </tex> проверка в условном операторе завершается за конечное время, то функция <tex> a(\varepsilon) </tex> вычислима для любого рационального <tex> \varepsilon </tex>.
}}
<tex> \Longrightarrow </tex>:
: Если число <tex> \alpha </tex> {{---}} рациональное, то необходимую последовательность можно получить, воспользовавшись стандартным алгоритмом перевода числа в двоичную систему счисления. Рассмотрим случай, когда <tex> \alpha \in \mathbb R \setminus \mathbb Q </tex>.
: Очевидно, двоичная запись целой части <tex> \alpha </tex> всегда вычислима (так как множество чисел, меньших <tex> \alpha </tex>, разрешимо, то можно перебрать все целые числа в порядке возрастания их абсолютных величин и найти наибольшее число, меньшее <tex> \alpha </tex>), поэтому будем считать, что <tex> \alpha \in (0; 1) </tex>.
: Напишем программу, которая по числу <tex> n </tex> вычисляет <tex> n </tex>-ный знак числа <tex> \alpha </tex> после запятой:
'''fun''' <tex>p(n)</tex>:
<tex> \Longleftarrow </tex>:
: Для любого рационального <tex> \varepsilon > 0 </tex>, найдем <tex> n: 2^{-n} < \varepsilon </tex>, тогда в качестве значения функции <tex> a(\varepsilon) </tex> можно взять часть последовательности знаков двоичной записи <tex> \alpha </tex> с <tex> n </tex> знаками после запятой.
}}
<tex> \Longrightarrow </tex>:
: Так как <tex> \alpha </tex> вычислимо, то, согласно предыдущей теореме, вычислима и его двоичная запись. Пусть <tex> r_n </tex> {{---}} часть последовательности знаков двоичной записи <tex> \alpha </tex> с <tex> n </tex> знаками после запятой. Данная последовательность вычислима, а также вычислимо сходится к <tex> \alpha </tex>, так как <tex> \mathbb N(\varepsilon) = \lceil -\log_2 \varepsilon \rceil</tex>.
<tex> \Longleftarrow </tex>:
: Пусть <tex> a(\varepsilon) = r_{N(\varepsilon)} </tex>, тогда <tex> \alpha </tex> вычислимо по определению.
}}
Число <tex> \alpha </tex> перечислимо снизу тогда и только тогда, когда существует вычислимая возрастающая последовательность рациональных чисел, пределом которой является <tex> \alpha </tex>.
|proof=
<tex>\RightarrowLongrightarrow</tex>:
: По определению <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>\LeftarrowLongleftarrow</tex>:
: Построим полуразрешитель для множества <tex> A </tex>:
'''fun''' <tex>p(x)</tex>:
'''return''' 1
: Если <tex> x \in A</tex>, то <tex> \alpha - x = t > 0 </tex>, и так как <tex> \exists N:\ \forall n > N |a_n - \alpha| < t </tex>, то программа вернет ответ при <tex> n > N </tex>.
}}
