689
правок
Изменения
→Свойства: еще две теоремы
<tex> \Longleftarrow </tex>:
Построим функцию <tex> a(\varepsilon) </tex>:
Так как <tex> A </tex> разрешимо, <tex> \alpha = \sup A </tex> и для любого <tex> x \in A </tex> проверка в условном операторе завершается за конечное время, то функция <tex> a(\varepsilon) </tex> вычислима для любого рационального <tex> \varepsilon </tex>.
}}
С учетом только что доказанной теоремы, далее при проверке на принадлежность числа <tex> x </tex> множеству <tex> A </tex> будем писать просто <tex> x < \alpha </tex>.
{{Теорема
|statement=
Число <tex> \alpha </tex> вычислимо тогда и только тогда, когда существует вычислимая последовательность рациональных чисел, вычислимо сходящаяся к <tex> \alpha </tex>знаков представляющей его двоичной записи вычислима. {{TODO|t=вычислимо сходящаяся}}
|proof=
<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> после запятой:
<tex>p(n)</tex>:
l = 0, r = 1
'''for''' <tex> k = 1..n </tex>:
<tex> m = \frac{l+r}2 </tex>
'''if''' <tex> m < \alpha</tex>:
l = m, t = 1
'''else''':
r = m, t = 0
'''return''' t
<tex> \Longleftarrow </tex>:
Для любого рационального <tex> \varepsilon > 0 </tex>, найдем <tex> n: 2^{-n} < \varepsilon </tex>, тогда в качестве значения функции <tex> a(\varepsilon) </tex> можно взять часть последовательности знаков двоичной записи <tex> \alpha </tex> с <tex> n </tex> знаками после запятой.
}}
{{Определение
|definition=
Последовательность рациональных чисел <tex> \{ r_n \} </tex> вычислимо сходится к <tex> \alpha </tex>, если существует вычислимая функция <tex> N: \mathbb Q \rightarrow \mathbb N </tex>, такая, что для любого рационального <tex> \varepsilon > 0 </tex> выполняется <tex>\forall n > N(\varepsilon): |r_n - \alpha| < \varepsilon </tex>.
}}
{{Теорема
|statement=
|proof=
<tex> \Longrightarrow </tex>:
Так как <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> \Longleftarrow </tex>:
Пусть <tex> a(\varepsilon) = r_{N(\varepsilon)} </tex>, тогда <tex> \alpha </tex> вычислимо по определению.
}}
{{Теорема
|statement=
Пусть числа <tex> \alpha, \beta </tex> вычислимы. Тогда также вычислимы числа <tex> \alpha + \beta </tex>, <tex> \alpha - \beta </tex>, <tex> \alpha \beta </tex> и <tex> \frac \alpha \beta </tex>.
|proof=
{{TODO|t=здесь должна появиться некоторая унылая арифметика}}
}}
