129
правок
Изменения
м
Нет описания правки
{{Теорема
|statement=
Число <tex> \alpha </tex> вычислимо тогда и только тогда, когда <tex>\iff</tex> множество <tex>A = \{x \in \mathbb Q \mid x < \alpha \} </tex> [[Разрешимые (рекурсивные) языки|разрешимо]].
|proof=
<tex> \Longrightarrow </tex>:
{{Теорема
|statement=
Число <tex> \alpha </tex> вычислимо тогда и только тогда, когда <tex>\iff</tex> последовательность знаков представляющей его двоичной записи вычислима.
|proof=
<tex> \Longrightarrow </tex>:
{{Теорема
|statement=
Число <tex> \alpha </tex> вычислимо тогда и только тогда, когда <tex>\iff</tex> существует вычислимая последовательность рациональных чисел, вычислимо сходящаяся к <tex> \alpha </tex>.
|proof=
<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>:
Далее, так как
<texdpi="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 \in \mathbb Q, |b_\beta| > |\beta| </tex> (<tex> b_\beta </tex>, очевидно, можно найти за конечное время), то
<texdpi="150"> f_{\alpha \beta}(\varepsilon) = f_{\alpha}(\dfrac \varepsilon {b_\beta}) f_{\beta}(\dfrac \varepsilon a) </tex>.
Убедимся в вычислимости числа <tex> \dfrac 1 \alpha </tex>:
{{Теорема
|statement=
Число <tex> \alpha </tex> перечислимо снизу тогда и только тогда, когда <tex>\iff</tex> существует вычислимая возрастающая последовательность рациональных чисел, пределом которой является <tex> \alpha </tex>.
|proof=
<tex>\Longrightarrow</tex>:
'''function''' <tex>p(x)</tex>:
'''for''' n in = <tex>1</tex> '''to''' <tex>\infty</tex>:
'''if''' <tex> x < a_n </tex>:
'''return''' 1
{{Теорема
|statement=
Число <tex> \alpha </tex> вычислимо тогда и только тогда, когда <tex>\iff</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> соответственно.
{{Определение
|definition=
Пусть <tex> A </tex> {{---}} некоторое перечислимое, но неразрешимое множество натуральных чисел. Занумеруем его элементы. '''Последовательностью Шпеккера''' <tex> \{q_n\} </tex> называется последовательность рациональных чисел, <tex>n</tex>-ный член которой определяется как <texdpi="150"> q_n = \sum\limits_{k=1}^{n} 2^{-A(n)-1} </tex>.
}}
Данная последовательность строго возрастает и ограничена числом <tex> 1 </tex>, следовательно, она сходится по признаку Вейерштрасса, она сходится.
{{Теорема
