36
правок
Изменения
Нет описания правки
'''for''' <tex> n = 1</tex> '''to''' <tex>\infty </tex>
'''if''' <tex> x < a \left(\dfrac{1}{n} \right) - \dfrac{1}{n} </tex>
'''return''' <tex>1</tex>
'''if''' <tex> x > a \left(\dfrac{1}{n} \right) + \dfrac{1}{n} </tex>
'''return''' <tex>0</tex>
<tex> \Longleftarrow </tex>:
: Построим функцию <tex> a(\varepsilon) </tex>
'''function''' <tex> a(\varepsilon) </tex>:
'''for''' <tex> x \in A </tex>
'''if''' <tex> x + \varepsilon \notin A </tex>
'''return''' <tex>x</tex>
: Так как <tex> A </tex> разрешимо, <tex> \alpha = \sup A </tex> и для любого <tex> x \in A </tex> проверка в условном операторе завершается за конечное время, то функция <tex> a(\varepsilon) </tex> вычислима для любого рационального <tex> \varepsilon </tex>.
Число <tex> \alpha </tex> вычислимо <tex>\iff</tex> последовательность знаков представляющей его двоичной записи вычислима.
|proof=
<tex> \Longrightarrow </tex>:
: Если число <tex> \alpha </tex> {{---}} рациональное, то необходимую последовательность можно получить, воспользовавшись стандартным алгоритмом перевода числа в двоичную систему счисления. Рассмотрим случай, когда <tex> \alpha \in \mathbb R \setminus \mathbb Q </tex>.
'''function''' <tex>p(n)</tex>:
<tex>l = 0, r = 1</tex>
'''for''' <tex> k = 1</tex> '''to''' <tex>n </tex>
<tex> m = \dfrac{l+r}{2} </tex>
'''if''' <tex> m < \alpha</tex>
<tex>l = m, t = 1</tex>
'''else'''
<tex>r = m, t = 0</tex> '''return''' <tex>t</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> \alpha </tex> вычислимо <tex>\iff</tex> существует вычислимая последовательность рациональных чисел, вычислимо сходящаяся к <tex> \alpha </tex>.
|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> вычислимо по определению.
Для того, чтобы получить приближение для результата операции, нам нужно выразить функцию-результат через приближения для операндов.
Заметим, что <tex> |(\alpha \pm \beta) - (a \pm b)| \le leqslant |\alpha - a| \pm |\beta - b| </tex>, для произвольных рациональных <tex> a, b </tex>, значит, в качестве необходимых функций для <tex> \alpha + \beta </tex> и <tex> \alpha - \beta </tex> можно взять
<tex > f_{\alpha + \beta}(\varepsilon) = f_{\alpha}\left(\dfrac {\varepsilon} {2}\right) + f_{\beta}\left(\dfrac {\varepsilon} {2}\right) </tex>
Далее, так как
<tex> |\alpha \beta - ab| = |(\alpha \beta - a \beta) + (a \beta - ab)| \le leqslant |\beta||\alpha - a| + |a||\beta - b| \le leqslant |b_\beta||\alpha - a| + |a||\beta - b|</tex>,
где <tex>b_\beta</tex> {{---}} наименьшее рациональное число, большее <tex>\beta</tex> по модулю (т.е. <tex> b_\beta \in \mathbb Q, |b_\beta| > |\beta| </tex>), то
Убедимся в вычислимости числа <tex> \dfrac {1} {\alpha} </tex>:
<tex> \left|\dfrac {1} {\alpha} - \dfrac{1}{a}\right| \le leqslant \dfrac {|a - \alpha|}{a a_\alpha} </tex>, где <tex> a_\alpha \in \mathbb Q, |a_\alpha| < |\alpha| </tex>.
<tex> f_{\dfrac frac {1} {\alpha}}(\varepsilon) = f_{\alpha}(\varepsilon a a_\alpha) </tex>.
Отсюда, <tex> \dfrac {\alpha} {\beta} = \dfrac{1} {\alpha} \beta </tex> также вычислимо.
'''return''' <tex> p_n\left(\dfrac {\varepsilon} {2}\right) </tex>
Так как <tex> \left|\alpha - p_{n}\left(\dfrac {\varepsilon} {2}\right)\right| < |\alpha - r(n)| + \left|r(n) - p_n\left(\dfrac {\varepsilon} {2}\right)\right| </tex>, оба слагаемых меньше <tex> \dfrac {\varepsilon} {2} </tex> (первое {{---}} по выбору <tex> n </tex>, второе {{---}} в силу вычислимости <tex> p_n </tex>), то <tex> \left|\alpha - p_n\left(\dfrac \varepsilon 2\right)\right| < \varepsilon </tex>, и <tex> a(\varepsilon) </tex> действительно вычисляет требуемое приближение.
}}
Число <tex> \alpha </tex> перечислимо снизу <tex>\iff</tex> существует вычислимая возрастающая последовательность рациональных чисел, пределом которой является <tex> \alpha </tex>.
|proof=
<tex>\Longrightarrow</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_{\dfracfrac{1}{n}} </tex>.
<tex>\Longleftarrow</tex>:
: Построим полуразрешитель для множества <tex> A </tex>:
'''for''' n = <tex>1</tex> '''to''' <tex>\infty</tex>
'''if''' <tex> x < a_n </tex>
'''return''' <tex>1</tex>
: Если <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>.
