129
правок
Изменения
Нет описания правки
Число <tex> \alpha </tex> вычислимо <tex>\iff</tex> множество <tex>A = \{x \in \mathbb Q \mid x < \alpha \} </tex> [[Разрешимые (рекурсивные) языки|разрешимо]].
|proof=
<tex> \Longrightarrow </tex>:
: Если <tex> \alpha </tex> {{---}} рациональное, то существует тривиальный разрешитель для <tex> A </tex>, который просто сравнивает полученный элемент с <tex> \alpha </tex>.
'''function''' <tex> p(x)</tex>:
'''for''' <tex> n = 1</tex> '''to''' <tex>\infty </tex>
'''if''' <tex> x < a(\dfrac1ndfrac{1}{n}) - \dfrac1n dfrac{1}{n} </tex>
'''return''' 1
'''if''' <tex> x > a(\dfrac1ndfrac{1}{n}) + \dfrac1n dfrac{1}{n} </tex>
'''return''' 0
<tex> \Longleftarrow </tex>:
: Пусть <tex dpi="150"> a(\varepsilon) = r_{N(\varepsilon)} </tex>, тогда <tex> \alpha </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 dpi="150"> f_{\alpha + \beta}(\varepsilon) = f_{\alpha}(\dfrac \varepsilon 2) + f_{\beta}(\dfrac \varepsilon 2) </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 dpi="150"> f_{\alpha \beta}(\varepsilon) = f_{\alpha}(\dfrac \varepsilon {b_\beta}) f_{\beta}(\dfrac \varepsilon a) </tex>.
Убедимся в вычислимости числа <tex> \dfrac 1 \alpha </tex>:
<tex dpi="150"> |\dfrac 1 \alpha - \dfrac1a| \le \dfrac {|a - \alpha|}{a a_\alpha} </tex>, где <tex> a_\alpha \in \mathbb Q, |a_\alpha| < |\alpha| </tex>.
<tex dpi="150"> f_{\frac 1 \alpha}(\varepsilon) = f_{\alpha}(\varepsilon a a_\alpha) </tex>.
Отсюда, <tex> \dfrac \alpha \beta = \dfrac1 \alpha \beta </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 dpi="150"> a_n = x_{\frac{1}{n}} </tex>.
<tex>\Longleftarrow</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>.
}}
