129
правок
Изменения
м
Нет описания правки
: Очевидно, двоичная запись целой части <tex> \alpha </tex> всегда вычислима (так как множество чисел, меньших <tex> \alpha </tex>, разрешимо, то можно перебрать все целые числа в порядке возрастания их абсолютных величин и найти наибольшее число, меньшее <tex> \alpha </tex>), поэтому будем считать, что <tex> \alpha \in (0; 1) </tex>.
: Напишем программу, которая по числу <tex> n </tex> вычисляет <tex> n </tex>-ный знак в двоичном представлении числа <tex> \alpha </tex> после запятой:
'''function''' <tex>p(n)</tex>:
<tex dpi="150"> f_{\alpha - \beta}(\varepsilon) = f_{\alpha}(\dfrac \varepsilon 2) - f_{\beta}(\dfrac \varepsilon 2) </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 dpi="150"> |\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</tex> {{---}} наименьшее рациональное число, большее <tex>\beta</tex> по модулю (т.е. <tex> b_\beta \in \mathbb Q, |b_\beta| > |\beta| </tex> (<tex> b_\beta </tex>, очевидно, можно найти за конечное время), то
<tex dpi="150"> f_{\alpha \beta}(\varepsilon) = f_{\alpha}(\dfrac \varepsilon {b_\beta}) f_{\beta}(\dfrac \varepsilon a) </tex>.
{{Теорема
|statement=
Предел вычислимо сходящейся вычислимой последовательности <tex> r_n </tex> вычислимых чисел вычислим.
|proof=
Пусть рассматриваемая последовательность {{---}} <tex> r_n </tex>, и <tex> \alpha = \lim\limits_{n \to \infty} r_n </tex>. Запишем формально данные нам условия:
<tex> \forall \varepsilon_1 > 0\ \forall n > (\varepsilon_1): |r(n) - \alpha| < \varepsilon_1 </tex>
{{Определение
|definition=
Пусть <tex> A </tex> {{---}} некоторое перечислимое, но неразрешимое множество натуральных чисел. Занумеруем Пронумеруем его элементы. '''Последовательностью Шпеккера''' <tex> \{q_n\} </tex> называется последовательность рациональных чисел, <tex>n</tex>-ный член которой определяется как <tex dpi="150"> q_n = \sum\limits_{k=1}^{n} 2^{-A(n)-1} </tex>.
}}
<tex> q </tex> перечислимо снизу, как предел возрастающей вычислимой последовательности рациональных чисел.
Допустим теперь, что <tex> q </tex> {{---}} вычислимо.
Пусть <tex> A = \{p \mid p(p) = 1\}</tex>. Рассмотрим двоичную запись числа <tex> q </tex>, если ее <tex> n </tex>-ный знак после запятой равен 1, то <tex> n \in A </tex>, иначе {{---}} <tex> n \notin A </tex>. Мы построили разрешитель для множества <tex> A </tex>. Тем не менее, мы знаемизвестно, что <tex> A </tex> {{---}} неразрешимое множество, и а это невозможно, значит, <tex> q </tex> {{---}} невычислимо.
}}
