129
правок
Изменения
Нет описания правки
: В противном случае, построим разрешитель для <tex> A </tex>:
'''funfunction'''<tex> p(x)</tex>: '''for''' <tex> n = 1.. </tex> '''to''' <tex>\infty </tex>:
'''if''' <tex> x < a(\dfrac1n) - \dfrac1n </tex>:
'''return''' 1
: Построим функцию <tex> a(\varepsilon) </tex>:
'''funfunction''' <tex> a(\varepsilon) </tex>:
'''for''' <tex> x \in A </tex>:
'''if''' <tex> x + \varepsilon \notin A </tex>:
: Напишем программу, которая по числу <tex> n </tex> вычисляет <tex> n </tex>-ный знак числа <tex> \alpha </tex> после запятой:
'''funfunction''' <tex>p(n)</tex>:
l = 0, r = 1
'''for''' <tex> k = 1..</tex> '''to''' <tex>n </tex>:
<tex> m = \dfrac{l+r}2 </tex>
'''if''' <tex> m < \alpha</tex>:
<tex> \Longleftarrow </tex>:
: Пусть <texdpi="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> можно взять
<texdpi="150"> f_{\alpha + \beta}(\varepsilon) = f_{\alpha}(\dfrac \varepsilon 2) + f_{\beta}(\dfrac \varepsilon 2) </tex>
и
<texdpi="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> \dfrac 1 \alpha </tex>:
<texdpi="150"> |\dfrac 1 \alpha - \dfrac1a| \le \dfrac {|a - \alpha|}{a a_\alpha} </tex>, где <tex> a_\alpha \in \mathbb Q, |a_\alpha| < |\alpha| </tex>.
<texdpi="150"> f_{\dfrac frac 1 \alpha}(\varepsilon) = f_{\alpha}(\varepsilon a a_\alpha) </tex>.
Отсюда, <tex> \dfrac \alpha \beta = \dfrac1 \alpha \beta </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>.
Построим функцию <tex> a(\varepsilon) </tex>, которая дает приближение к <tex> \alpha </tex> с точностью до <tex> \varepsilon </tex>:
'''funfunction''' <tex> a(\varepsilon) </tex>:
n = <tex> N(\dfrac \varepsilon 2) + 1 </tex>
'''return''' <tex> p_n(\dfrac \varepsilon 2) </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>. Тогда можно взять, например, последовательность <texdpi="150"> a_n = x_{\dfrac frac{1 }{n}} </tex>.
<tex>\Longleftarrow</tex>:
: Построим полуразрешитель для множества <tex> A </tex>:
'''funfunction''' <tex>p(x)</tex>: '''for''' n in <tex>1..</tex> '''to''' <tex>\infty</tex>:
'''if''' <tex> x < a_n </tex>:
'''return''' 1
== Последовательность Шпеккера ==
Множество всех программ счетносчётно, поэтому множество вычислимых чисел также счетносчётно. Однако, множество вещественных чисел несчетнонесчётно, значит, существуют невычислимые вещественные числа. Построим явно пример такого числа.
{{Определение
== Источники информации ==
* ''Верещагин Н. К., Шень А.'' {{---}} Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции — М.: МЦНМО, 1999 {{--- С}} стр. 14
* [http://en.wikipedia.org/wiki/Computable_number Computable number]
* [http://en.wikipedia.org/wiki/Specker_sequence Specker sequence]
[[Категория: Теория формальных языков]]
[[Категория: Теория вычислимости]]
