Вычислимые числа

В математике натуральные, целые и рациональные числа являются конструктивными объектами, поэтому их использование в теории вычислимости не требует особых уточнений. В то же время, действительные числа, которые необходимы для применения методов математического анализа, определяются неконструктивно. Предложенный далее метод позволяет построить конструктивные объекты, во многом схожие с обычными действительными числами.

Вычислимые числа

Определение:

Действительное число [math] \alpha [/math] называется вычислимым (computable number), если существует вычислимая функция [math] a: \mathbb Q \rightarrow \mathbb Q [/math], такая, что [math]|\alpha - a(\varepsilon)| \lt \varepsilon [/math] для любого рационального [math] \varepsilon \gt 0 [/math].

Свойства

Теорема:

Число [math] \alpha [/math] вычислимо тогда и только тогда, когда множество [math]A = \{x \in Q \mid x \lt \alpha \} [/math] разрешимо.

Доказательство:

[math]\triangleright[/math]

[math] \Longrightarrow [/math]: Если [math] \alpha [/math] — рациональное, то существует тривиальный разрешитель для [math] A [/math], который просто сравнивает полученный элемент с [math] \alpha [/math]. В противном случае, построим разрешитель для [math] A [/math]: [math]p(x)[/math]: for [math] n = 1.. \infty [/math]: if [math] x \lt a(\frac1n) - \frac1n [/math]: return 1 if [math] x \gt a(\frac1n) + \frac1n [/math]: return 0 [math] \Longleftarrow [/math]: Построим функцию [math] a(\varepsilon) [/math]: [math] a(\varepsilon) [/math]: for [math] x \in A [/math]: if [math] x + \varepsilon \notin A [/math]: return x Так как [math] A [/math] разрешимо, [math] \alpha = \sup A [/math] и для любого [math] x \in A [/math] проверка в условном операторе завершается за конечное время, то функция [math] a(\varepsilon) [/math] вычислима для любого рационального [math] \varepsilon [/math].

[math]\triangleleft[/math]

Важное замечание: построенное нами доказательство неконструктивно, так как мы не знаем наперед, рационально ли число [math] \alpha [/math], и уж тем более не пытаемся понять в случае его рациональности, чему именно оно равно. Но, так как мы ставим целью исследование свойств вычислимых чисел, а не явное построение соответствующих этим свойствам программ, то нам это доказательство полностью подходит.

С учетом только что доказанной теоремы, далее при проверке на принадлежность числа [math] x [/math] множеству [math] A [/math] будем писать просто [math] x \lt \alpha [/math].

Теорема:

Число [math] \alpha [/math] вычислимо тогда и только тогда, когда последовательность знаков представляющей его двоичной записи вычислима.

Доказательство:

[math]\triangleright[/math]

[math] \Longrightarrow [/math]: Если число [math] \alpha [/math] — рациональное, то необходимую последовательность можно получить, воспользовавшись стандартным алгоритмом перевода числа в двоичную систему счисления. Рассмотрим случай, когда [math] \alpha \in \mathbb R \setminus \mathbb Q [/math]. Очевидно, двоичная запись целой части [math] \alpha [/math] всегда вычислима (так как множество чисел, меньших [math] \alpha [/math], разрешимо, то можно перебрать все целые числа в порядке возрастания их абсолютных величин и найти наибольшее число, меньшее [math] \alpha [/math]), поэтому будем считать, что [math] \alpha \in (0; 1) [/math]. Напишем программу, которая по числу [math] n [/math] вычисляет [math] n [/math]-ный знак числа [math] \alpha [/math] после запятой: [math]p(n)[/math]: l = 0, r = 1 for [math] k = 1..n [/math]: [math] m = \frac{l+r}2 [/math] if [math] m \lt \alpha[/math]: l = m, t = 1 else: r = m, t = 0 return t [math] \Longleftarrow [/math]: Для любого рационального [math] \varepsilon \gt 0 [/math], найдем [math] n: 2^{-n} \lt \varepsilon [/math], тогда в качестве значения функции [math] a(\varepsilon) [/math] можно взять часть последовательности знаков двоичной записи [math] \alpha [/math] с [math] n [/math] знаками после запятой.

[math]\triangleleft[/math]

Определение:

Последовательность рациональных чисел [math] \{ r_n \} [/math] вычислимо сходится к [math] \alpha [/math], если существует вычислимая функция [math] N: \mathbb Q \rightarrow \mathbb N [/math], такая, что для любого рационального [math] \varepsilon \gt 0 [/math] выполняется [math]\forall n \gt N(\varepsilon): |r_n - \alpha| \lt \varepsilon [/math].

Теорема:

Число [math] \alpha [/math] вычислимо тогда и только тогда, когда существует вычислимая последовательность рациональных чисел, вычислимо сходящаяся к [math] \alpha [/math].

Доказательство:

[math]\triangleright[/math]

[math] \Longrightarrow [/math]: Так как [math] \alpha [/math] вычислимо, то, согласно предыдущей теореме, вычислима и его двоичная запись. Пусть [math] r_n [/math] — часть последовательности знаков двоичной записи [math] \alpha [/math] с [math] n [/math] знаками после запятой. Данная последовательность вычислима, а также вычислимо сходится к [math] \alpha [/math], так как [math] N(\varepsilon) = \lceil -\log_2 \varepsilon \rceil[/math]. [math] \Longleftarrow [/math]: Пусть [math] a(\varepsilon) = r_{N(\varepsilon)} [/math], тогда [math] \alpha [/math] вычислимо по определению.

[math]\triangleleft[/math]

Теорема:

Пусть числа [math] \alpha, \beta [/math] вычислимы. Тогда также вычислимы числа [math] \alpha + \beta [/math], [math] \alpha - \beta [/math], [math] \alpha \beta [/math] и [math] \frac \alpha \beta [/math].

Доказательство:

[math]\triangleright[/math]

В пределах этого доказательства будем обозначать функцию-приближение для произвольного вычислимого числа [math] x [/math] как [math] f_x [/math]. Для того, чтобы получить приближение для результата операции, нам нужно выразить функцию-результат через приближения для операндов. Заметим, что [math] |(\alpha \pm \beta) - (a \pm b)| \le |\alpha - a| \pm |\beta - b| [/math], для произвольных рациональных [math] a, b [/math], значит, в качестве необходимых функций для [math] \alpha + \beta [/math] и [math] \alpha - \beta [/math] можно взять [math] f_{\alpha + \beta}(\varepsilon) = f_{\alpha}(\frac \varepsilon 2) + f_{\beta}(\frac \varepsilon 2) [/math] и [math] f_{\alpha - \beta}(\varepsilon) = f_{\alpha}(\frac \varepsilon 2) - f_{\beta}(\frac \varepsilon 2) [/math] соответственно (при подстановке в неравенство [math] f_{\alpha} [/math] и [math] f_{\beta} [/math] вместо [math] a [/math] и [math] b [/math] каждый модуль в правой части не превосходит [math] \frac \varepsilon 2 [/math], поэтому, [math] f_{\alpha \pm \beta} [/math] не превосходит [math] \varepsilon [/math]). Далее, так как [math] |\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|[/math], где [math] b_\beta \in \mathbb Q, |b_\beta| \gt |\beta| [/math] ([math] b_\beta [/math], очевидно, можно найти за конечное время), то [math] f_{\alpha \beta}(\varepsilon) = f_{\alpha}(\frac \varepsilon {b_\beta}) f_{\beta}(\frac \varepsilon a) [/math]. Убедимся в вычислимости числа [math] \frac 1 \alpha [/math]: [math] |\frac 1 \alpha - \frac1a| \le \frac {|a - \alpha|}{a a_\alpha} [/math], где [math] a_\alpha \in \mathbb Q, |a_\alpha| \lt |\alpha| [/math]. [math] f_{\frac 1 \alpha}(\varepsilon) = f_{\alpha}(\varepsilon a a_\alpha) [/math]. Отсюда, [math] \frac \alpha \beta = \frac1 \alpha \beta [/math] также вычислимо.

[math]\triangleleft[/math]

Теорема:

Корень многочлена с вычислимыми коэффициентами вычислим.

Доказательство:

[math]\triangleright[/math]

Пусть [math] x [/math] — корень многочлена [math] P(x) [/math] с вычислимыми коэффициентами. Если [math] x \in \mathbb Q [/math], то его можно найти точно, перебрав все рациональные числа. Иначе, выберем некоторый интервал [math] [a; b]: x \in [a; b] [/math] ([math] a, b [/math] — вычислимы), достаточно малый, чтобы полином [math] P(x) [/math] был монотонным на отрезках [math] [a; x] [/math] и [math] [x; b] [/math]. Заметим, что для вычислимого [math] t [/math] значение [math] P(t) [/math] также вычислимо, так как в процессе его вычисления используются только операции, вычислимость значений которых уже была ранее доказана. Теперь, если полином имеет разные знаки на отрезках [math] [a; x] [/math] и [math] [x; b] [/math], то для поиска [math] x [/math] можно воспользоваться двоичным поиском для поиска нуля на [math] [a; b] [/math], иначе — троичным поиском для поиска минимума или максимума на [math] [a; b] [/math]. Останавливая тот или иной алгоритм, когда текущая длина интервала становится меньше [math] \varepsilon [/math] и возвращая левую границу в качестве ответа, получаем функцию [math] a_x(\varepsilon) [/math].

[math]\triangleleft[/math]

Теорема:

Предел вычислимо сходящейся вычислимой последовательности вычислимых чисел вычислим.

Доказательство:

[math]\triangleright[/math]

Пусть рассматриваемая последовательность — [math] r_n [/math], и [math] \alpha = \lim\limits_{n \to \infty} r_n [/math]. Запишем формально данные нам условия: [math] \forall \overline \varepsilon_1 \gt 0\ \forall n \gt N(\varepsilon_1): |r(n) - \alpha| \lt \varepsilon_1 [/math] [math] \forall n\ \forall \varepsilon_2 \gt 0\ |r(n) - p_n(\varepsilon_2)| \lt \varepsilon_2 [/math] Здесь функции [math] N(\varepsilon_1) [/math], [math] r(n) [/math] и все [math] p_n(\varepsilon_2) [/math] вычислимы. Построим функцию [math] a(\varepsilon) [/math], которая дает приближение к [math] \alpha [/math] с точностью до [math] \varepsilon [/math]: [math] a(\varepsilon) [/math]: n = [math] N(\frac \varepsilon 2) + 1 [/math] return [math] p_n(\frac \varepsilon 2) [/math] Так как [math] |\alpha - p_n(\frac \varepsilon 2)| \lt |\alpha - r(n)| + |r(n) - p_n(\frac \varepsilon 2)| [/math], первое слагаемое меньше [math] \frac \varepsilon 2 [/math] по выбору [math] n [/math], второе — в силу вычислимости [math] p_n [/math], то [math] |\alpha - p_n(\frac \varepsilon 2)| \lt \varepsilon [/math], и [math] a(\varepsilon) [/math] действительно вычисляет требуемое приближение.

[math]\triangleleft[/math]

Перечислимые числа

Определение:

Действительное число [math] \alpha [/math] называется перечислимым снизу (recursively enumerable number), если множество [math] \{ a \in \mathbb Q \mid a \lt \alpha \} [/math] перечислимо.

Определение:

Действительное число [math] \alpha [/math] называется перечислимым сверху, если множество [math] \{ a \in \mathbb Q \mid a \gt \alpha \} [/math] перечислимо.

Свойства

Теорема:

Число [math] \alpha [/math] перечислимо снизу тогда и только тогда, когда существует вычислимая возрастающая последовательность рациональных чисел, пределом которой является [math] \alpha [/math].

Доказательство:

[math]\triangleright[/math]

[math]\Rightarrow[/math]: Так как [math] A = \{ a \in \mathbb Q \mid a \lt \alpha \} [/math] перечислимо, то можно перечислить его элементы в возрастающем порядке, они и дают нам необходимую последовательность, так как ее пределом будет [math] \lim \limits_{n \to \infty} a_n = \sup A = \alpha [/math]. [math]\Leftarrow[/math]: Построим полуразрешитель для множества [math] A [/math]: p(x): for n in [math]1..\infty[/math]: if [math] x \lt a_n [/math]: return 1 Если [math] x \in A[/math], то [math] \alpha - x = t \gt 0 [/math], и так как [math] \exists N:\ \forall n \gt N |a_n - \alpha| \lt t [/math], то программа вернет ответ при [math] n \gt N [/math].

[math]\triangleleft[/math]

Теорема:

Число [math] \alpha [/math] вычислимо тогда и только тогда, когда оно перечислимо сверху и снизу.

Доказательство:

[math]\triangleright[/math]

Обозначим множества [math] \{a \in \mathbb Q \mid a \lt \alpha \} [/math] и [math] \{a \in \mathbb Q \mid a \gt \alpha \} [/math] за [math] A [/math] и [math] B [/math] соответственно. Если [math] \alpha [/math] рационально, то необходимые (полу)разрешатели строятся тривиально. В противном случае, так как [math] B = \mathbb Q \setminus A[/math], то перечислимость множеств [math] A [/math] и [math] B [/math] равносильна разрешимости множества [math] A [/math], которая, в свою очередь, равносильна вычислимости [math] \alpha [/math].

[math]\triangleleft[/math]

Последовательность Шпеккера

Очевидно, множество вычислимых чисел счетно, так как его мощность можно ограничить сверху мощностью не более чем счетной степени множества [math] \mathbb Q [/math]. Однако, множество вещественных чисел несчетно, значит, существуют невычислимые вещественные числа. Построим явно пример такого числа.

Определение:

Пусть [math] A [/math] — некоторое перечислимое, но неразрешимое множество натуральных чисел. Занумеруем его элементы. Последовательностью Шпеккера [math] \{q_n\} [/math] называется последовательность рациональных чисел, [math]n[/math]-ный член которой определяется как [math] q_n = \sum\limits_{k=1}^{n} 2^{-A(n)-1} [/math].

Данная последовательность строго возрастает и ограничена числом [math] 1 [/math], следовательно, по признаку Вейерштрасса, она сходится.

Теорема:

Число [math] q = \lim\limits_{n \to \infty} q_n [/math] перечислимо снизу, но невычислимо.

Доказательство:

[math]\triangleright[/math]

[math] q [/math] перечислимо снизу, как предел возрастающей вычислимой последовательности рациональных чисел. Допустим теперь, что [math] q [/math] вычислимо. Пусть [math] A = \{p \mid p(p) = 1\}[/math]. Рассмотрим двоичную запись числа [math] q [/math], если ее [math] n [/math]-ный знак после запятой равен 1, то [math] n \in A [/math], иначе — [math] n \notin A [/math]. Мы построили разрешатель для множества [math] A [/math]. Тем не менее, мы знаем, что [math] A [/math] — неразрешимое множество, и это невозможно, значит, [math] q [/math] невычислимо.

[math]\triangleleft[/math]

Ссылки

• Верещагин Н. К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции — М.: МЦНМО, 1999 - С. 14
• http://en.wikipedia.org/wiki/Computable_number
• http://en.wikipedia.org/wiki/Specker_sequence