129
правок
Изменения
м
дроби больше
<tex>p(x)</tex>:
'''for''' <tex> n = 1.. \infty </tex>:
'''if''' <tex> x < a(\frac1ndfrac1n) - \frac1n dfrac1n </tex>:
'''return''' 1
'''if''' <tex> x > a(\frac1ndfrac1n) + \frac1n dfrac1n </tex>:
'''return''' 0
l = 0, r = 1
'''for''' <tex> k = 1..n </tex>:
<tex> m = \fracdfrac{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> \frac 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}(\frac dfrac \varepsilon 2) + f_{\beta}(\frac dfrac \varepsilon 2) </tex>
и
<tex> f_{\alpha - \beta}(\varepsilon) = f_{\alpha}(\frac dfrac \varepsilon 2) - f_{\beta}(\frac dfrac \varepsilon 2) </tex>
соответственно (при подстановке в неравенство <tex> f_{\alpha} </tex> и <tex> f_{\beta} </tex> вместо <tex> a </tex> и <tex> b </tex> каждый модуль в правой части не превосходит <tex> \frac dfrac \varepsilon 2 </tex>, поэтому, <tex> f_{\alpha \pm \beta} </tex> не превосходит <tex> \varepsilon </tex>).
Далее, так как
где <tex> b_\beta \in Q, |b_\beta| > |\beta| </tex> (<tex> b_\beta </tex>, очевидно, можно найти за конечное время), то
<tex> f_{\alpha \beta}(\varepsilon) = f_{\alpha}(\frac dfrac \varepsilon {b_\beta}) f_{\beta}(\frac dfrac \varepsilon a) </tex>.
Убедимся в вычислимости числа <tex> \frac dfrac 1 \alpha </tex>:
<tex> |\frac dfrac 1 \alpha - \frac1adfrac1a| \le \frac dfrac {|a - \alpha|}{a a_\alpha} </tex>, где <tex> a_\alpha \in Q, |a_\alpha| < |\alpha| </tex>.
<tex> f_{\frac dfrac 1 \alpha}(\varepsilon) = f_{\alpha}(\varepsilon a a_\alpha) </tex>.
Отсюда, <tex> \frac dfrac \alpha \beta = \frac1 dfrac1 \alpha \beta </tex> также вычислимо.
}}
<tex> a(\varepsilon) </tex>:
n = <tex> N(\frac dfrac \varepsilon 2) + 1 </tex> '''return''' <tex> p_n(\frac dfrac \varepsilon 2) </tex>
Так как <tex> |\alpha - p_n(\frac dfrac \varepsilon 2)| < |\alpha - r(n)| + |r(n) - p_n(\frac dfrac \varepsilon 2)| </tex>, первое слагаемое меньше <tex> \frac dfrac \varepsilon 2 </tex> по выбору <tex> n </tex>, второе {{---}} в силу вычислимости <tex> p_n </tex>, то <tex> |\alpha - p_n(\frac dfrac \varepsilon 2)| < \varepsilon </tex>, и <tex> a(\varepsilon) </tex> действительно вычисляет требуемое приближение.
}}
По определению <tex> \alpha </tex>, множество <tex> A = \{ a \in 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_{\frac dfrac 1 n} </tex>.
<tex>\Leftarrow</tex>:
