689
правок
Изменения
м
→Свойства: minor fixes
<tex> \Longrightarrow </tex>:
Если <tex> \alpha </tex> {{---}} рациональное, то существует тривиальный разрешатель разрешитель для <tex> A </tex>, который просто сравнивает полученный элемент с <tex> \alpha </tex>.
В противном случае, построим разрешатель разрешитель для <tex> A </tex>:
<tex>p(x)</tex>:
Так как <tex> A </tex> разрешимо, <tex> \alpha = \sup A </tex> и для любого <tex> x \in A </tex> проверка в условном операторе завершается за конечное время, то функция <tex> a(\varepsilon) </tex> вычислима для любого рационального <tex> \varepsilon </tex>.
}}
'''Важное замечание''': построенное нами доказательство неконструктивно, так как мы не знаем наперед, рационально ли число <tex> \alpha </tex>, и уж тем более не пытаемся понять в случае его рациональности, чему именно оно равно. Но, так как мы ставим целью исследование свойств вычислимых чисел, а не явное построение соответствующих этим свойствам программ, то нам это доказательство полностью подходит.
С учетом только что доказанной теоремы, далее при проверке на принадлежность числа <tex> x </tex> множеству <tex> A </tex> будем писать просто <tex> x < \alpha </tex>.
{{Теорема
|statement=
Пусть числа <tex> \alpha, \beta </tex> вычислимы. Тогда также вычислимы числа <tex> \alpha + \beta </tex>, <tex> \alpha - \beta </tex>, <tex> \alpha \beta </tex> и <tex> \frac \alpha \beta </tex>.
|proof=
В пределах этого доказательства будем обозначать функцию-приближение для произвольного вычислимого числа <tex> x </tex> как <tex> f_x </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> a_f_{\alpha + \beta}(\varepsilon) = a_f_{\alpha}(\frac \varepsilon 2) + a_f_{\beta}(\frac \varepsilon 2) </tex>
и
<tex> a_f_{\alpha - \beta}(\varepsilon) = a_f_{\alpha}(\frac \varepsilon 2) - a_f_{\beta}(\frac \varepsilon 2) </tex>
соответственно(при подстановке в неравенство <tex> f_{\alpha} </tex> и <tex> f_{\beta} </tex> вместо <tex> a </tex> и <tex> b </tex> каждый модуль в правой части не превосходит <tex> \frac \varepsilon 2 </tex>, поэтому, <tex> f_{\alpha \pm \beta} </tex> не превосходит <tex> \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> a_f_{\alpha \beta}(\varepsilon) = a_f_{\alpha}(\frac \varepsilon {b_\beta}) a_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> a_f_{\frac 1 \alpha}(\varepsilon) = a_f_{\alpha}(\varepsilon a a_\alpha) </tex>.
Отсюда, <tex> \frac \alpha \beta = \frac1 \alpha \beta </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> t </tex> значение <tex> P(t) </tex> также вычислимо, так как в процессе его вычисления используются только операции, вычислимость значений которых уже была ранее доказана.
Теперь, если полином имеет разные знаки на отрезках <tex> [a; x] </tex> и <tex> [x; b] </tex>, то для поиска <tex> x </tex> можно воспользоваться двоичным поиском для поиска нуля на <tex> [a; b] </tex>, иначе {{---}} троичным поиском для поиска минимума или максимума на <tex> [a; b] </tex>. В обоих операциях
Останавливая тот или иной алгоритм при длине текущего , когда текущая длина интервала, меньшей становится меньше <tex> \varepsilon </tex>и возвращая левую границу в качестве ответа, получаем функцию <tex> a_x(\varepsilon) </tex>.
}}
