129
правок
Изменения
м
отформатированы дроби
'''function''' <tex> p(x)</tex>:
'''for''' <tex> n = 1</tex> '''to''' <tex>\infty </tex>
'''if''' <tex> x < a\left(\dfrac{1}{n}\right) - \dfrac{1}{n} </tex>
'''return''' 1
'''if''' <tex> x > a\left(\dfrac{1}{n}\right) + \dfrac{1}{n} </tex>
'''return''' 0
l = 0, r = 1
'''for''' <tex> k = 1</tex> '''to''' <tex>n </tex>
<tex> m = \dfrac{l+r}{2 } </tex>
'''if''' <tex> m < \alpha</tex>
l = m, t = 1
|statement=
Пусть числа <tex> \alpha, \beta </tex> вычислимы. Тогда также вычислимы числа <tex> \alpha + \beta </tex>, <tex> \alpha - \beta </tex>, <tex> \alpha \beta </tex> и <tex> \dfrac {\alpha } {\beta } </tex>.
|proof=
В пределах этого доказательства будем обозначать функцию-приближение для произвольного вычислимого числа <tex> x </tex> как <tex> f_x </tex>.
Заметим, что <tex> |(\alpha \pm \beta) - (a \pm b)| \le |\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> f_{\alpha - \beta}(\varepsilon) = f_{\alpha}\left(\dfrac {\varepsilon } {2}\right) - f_{\beta}\left(\dfrac {\varepsilon } {2}\right) </tex>
соответственно (при подстановке в неравенство <tex> f_{\alpha} </tex> и <tex> f_{\beta} </tex> вместо <tex> a </tex> и <tex> b </tex> каждый модуль в правой части не превосходит <tex> \dfrac {\varepsilon } {2 } </tex>, поэтому <tex> f_{\alpha \pm \beta} </tex> не превосходит <tex> \varepsilon </tex>).
Далее, так как
где <tex>b_\beta</tex> {{---}} наименьшее рациональное число, большее <tex>\beta</tex> по модулю (т.е. <tex> b_\beta \in \mathbb Q, |b_\beta| > |\beta| </tex>), то
<tex> f_{\alpha \beta}(\varepsilon) = f_{\alpha}\left(\dfrac {\varepsilon } {b_\beta}\right) f_{\beta}\left(\dfrac {\varepsilon } {a}\right) </tex>.
Убедимся в вычислимости числа <tex> \dfrac {1 } {\alpha } </tex>:
<tex> \left|\dfrac {1 } {\alpha } - \dfrac1adfrac{1}{a}\right| \le \dfrac {|a - \alpha|}{a a_\alpha} </tex>, где <tex> a_\alpha \in \mathbb Q, |a_\alpha| < |\alpha| </tex>.
<tex> f_{\frac dfrac {1 } {\alpha}}(\varepsilon) = f_{\alpha}(\varepsilon a a_\alpha) </tex>.
Отсюда, <tex> \dfrac {\alpha } {\beta } = \dfrac1 dfrac{1} {\alpha } \beta </tex> также вычислимо.
}}
'''function''' <tex> a(\varepsilon) </tex>:
n = <tex> N\left(\dfrac {\varepsilon } {2}\right) + 1 </tex> '''return''' <tex> p_n\left(\dfrac {\varepsilon } {2}\right) </tex>
Так как <tex> \left|\alpha - p_np_{n}\left(\dfrac {\varepsilon } {2}\right)\right| < |\alpha - r(n)| + |r(n) - p_n\left(\dfrac {\varepsilon } {2}\right)| </tex>, оба слагаемых меньше <tex> \dfrac {\varepsilon } {2 } </tex> (первое {{---}} по выбору <tex> n </tex>, второе {{---}} в силу вычислимости <tex> p_n </tex>), то <tex> |\alpha - p_n\left(\dfrac \varepsilon 2\right)| < \varepsilon </tex>, и <tex> a(\varepsilon) </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_{\fracdfrac{1}{n}} </tex>.
<tex>\Longleftarrow</tex>:
