689
правок
Изменения
свойства вычислимых чисел все
Корень многочлена с вычислимыми коэффициентами вычислим.
|proof=
Пусть <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> 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>.
}}
Предел вычислимо сходящейся вычислимой последовательности вычислимых чисел вычислим.
|proof=
Пусть рассматриваемая последовательность {{---}} <tex> r_n </tex>, и <tex> \alpha = \lim\limits_{n \to \infty} r_n </tex>. Запишем формально данные нам условия:
<tex> \forall \overline \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>
Здесь функции <tex> N(\varepsilon_1) </tex>, <tex> r(n) </tex> и все <tex> p_n(\varepsilon_2) </tex> вычислимы.
Построим функцию <tex> a(\varepsilon) </tex>, которая дает приближение к <tex> \alpha </tex> с точностью до <tex> \varepsilon </tex>:
<tex> a(\varepsilon) </tex>:
n = <tex> N(\frac \varepsilon 2) + 1 </tex>
'''return''' <tex> p_n(\frac \varepsilon 2) </tex>
Так как <tex> |\alpha - p_n(\frac \varepsilon 2)| < |\alpha - r(n)| + |r(n) - p_n(\frac \varepsilon 2)| </tex>, первое слагаемое меньше <tex> \frac \varepsilon 2 </tex> по выбору <tex> n </tex>, второе {{---}} в силу вычислимости <tex> p_n </tex>, то <tex> |\alpha - p_n(\frac \varepsilon 2)| < \varepsilon </tex>, и <tex> a(\varepsilon) </tex> действительно вычисляет требуемое приближение.
}}
