129
правок
Изменения
м
Отмена #55702 + 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>.
}}
{{Теорема
|statement=
Число <tex> \alpha </tex> вычислимо тогда и только тогда, когда множество <tex>A = \{x \in \mathbb Q \mid x < \alpha \} </tex> [[Разрешимые (рекурсивные) языки|разрешимо]].
|proof=
<tex> \Longrightarrow </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> \Longrightarrow </tex>:
Так как <tex> \alpha </tex> вычислимо, то, согласно предыдущей теореме, вычислима и его двоичная запись. Пусть <tex> r_n </tex> {{---}} часть последовательности знаков двоичной записи <tex> \alpha </tex> с <tex> n </tex> знаками после запятой. Данная последовательность вычислима, а также вычислимо сходится к <tex> \alpha </tex>, так как <tex> \mathbb N(\varepsilon) = \lceil -\log_2 \varepsilon \rceil</tex>.
<tex> \Longleftarrow </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}(\dfrac \varepsilon {b_\beta}) f_{\beta}(\dfrac \varepsilon a) </tex>.
Убедимся в вычислимости числа <tex> \dfrac 1 \alpha </tex>:
<tex> |\dfrac 1 \alpha - \dfrac1a| \le \dfrac {|a - \alpha|}{a a_\alpha} </tex>, где <tex> a_\alpha \in \mathbb Q, |a_\alpha| < |\alpha| </tex>.
<tex> f_{\dfrac 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>.
Пусть рассматриваемая последовательность {{---}} <tex> r_n </tex>, и <tex> \alpha = \lim\limits_{n \to \infty} r_n </tex>. Запишем формально данные нам условия:
<tex> \forall \varepsilon_1 > 0\ \forall n > N(\varepsilon_1): |r(n) - \alpha| < \varepsilon_1 </tex>
<tex> \forall n\ \forall \varepsilon_2 > 0\ |r(n) - p_n(\varepsilon_2)| < \varepsilon_2 </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_{\dfrac 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>.
}}
