129
правок
Изменения
м
убрал mathbb для множеств
{{Определение
|definition=
Действительное число <tex> \alpha </tex> называется '''вычислимым''' (computable number), если существует [[Вычислимые функции|вычислимая функция]] <tex> a: \mathbb Q \rightarrow \mathbb Q </tex>, такая, что <tex>|\alpha - a(\varepsilon)| < \varepsilon </tex> для любого рационального <tex> \varepsilon > 0 </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>.
{{Определение
|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>.
}}
<tex> |\alpha \beta - ab| = |(\alpha \beta - a \beta) + (a \beta - ab)| \le |\beta||\alpha - a| + |a||\beta - b| \le |b_\beta||\alpha - a| + |a||\beta - b|</tex>,
где <tex> b_\beta \in \mathbb Q, |b_\beta| > |\beta| </tex> (<tex> b_\beta </tex>, очевидно, можно найти за конечное время), то
<tex> f_{\alpha \beta}(\varepsilon) = f_{\alpha}(\frac \varepsilon {b_\beta}) f_{\beta}(\frac \varepsilon a) </tex>.
Убедимся в вычислимости числа <tex> \frac 1 \alpha </tex>:
<tex> |\frac 1 \alpha - \frac1a| \le \frac {|a - \alpha|}{a a_\alpha} </tex>, где <tex> a_\alpha \in \mathbb Q, |a_\alpha| < |\alpha| </tex>.
<tex> f_{\frac 1 \alpha}(\varepsilon) = f_{\alpha}(\varepsilon a a_\alpha) </tex>.
Пусть <tex> x </tex> {{---}} корень многочлена <tex> P(x) </tex> с вычислимыми коэффициентами.
Если <tex> x \in \mathbb Q </tex>, то его можно найти точно, перебрав все рациональные числа.
Иначе, выберем некоторый интервал <tex> [a; b]: x \in [a; b] </tex> (<tex> a, b </tex> {{---}} вычислимы), достаточно малый, чтобы полином <tex> P(x) </tex> был монотонным на отрезках <tex> [a; x] </tex> и <tex> [x; b] </tex>.
{{Определение
|definition=
Действительное число <tex> \alpha </tex> называется '''перечислимым снизу''' (recursively enumerable number), если множество <tex> \{ a \in \mathbb Q \mid a < \alpha \} </tex> [[Перечислимые языки|перечислимо]].
}}
{{Определение
|definition=
Действительное число <tex> \alpha </tex> называется '''перечислимым сверху''', если множество <tex> \{ a \in \mathbb Q \mid a > \alpha \} </tex> перечислимо.
}}
<tex>\Rightarrow</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_{\frac 1 n} </tex>.
Число <tex> \alpha </tex> вычислимо тогда и только тогда, когда оно перечислимо сверху и снизу.
|proof=
Обозначим множества <tex> \{a \in \mathbb Q \mid a < \alpha \} </tex> и <tex> \{a \in \mathbb Q \mid a > \alpha \} </tex> за <tex> A </tex> и <tex> B </tex> соответственно.
Если <tex> \alpha </tex> рационально, то необходимые (полу)разрешители строятся тривиально.
В противном случае, так как <tex> B = \mathbb Q \setminus A</tex>, то перечислимость множеств <tex> A </tex> и <tex> B </tex> равносильна разрешимости множества <tex> A </tex>, которая, в свою очередь, равносильна вычислимости <tex> \alpha </tex>.
}}
