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

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

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

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

Действительное число называется вычислимым (computable number), если существует вычислимая функция , такая, что для любого рационального .

Свойства

Теорема:

Число вычислимо тогда и только тогда, когда множество разрешимо.

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

[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] \alpha [/math], и уж тем более не пытаемся понять в случае его рациональности, чему именно оно равно. Но, так как мы ставим целью исследование свойств вычислимых чисел, а не явное построение соответствующих этим свойствам программ, то нам это доказательство полностью подходит.

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

Теорема:

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

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

[math] \Longrightarrow [/math]:

Если число [math] \alpha [/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] \Longrightarrow [/math]:

Так как [math] \alpha [/math] вычислимо, то, согласно предыдущей теореме, вычислима и его двоичная запись. Пусть [math] r_n [/math] — часть последовательности знаков двоичной записи [math] \alpha [/math] с [math] n [/math] знаками после запятой. Данная последовательность вычислима, а также вычислимо сходится к [math] \alpha [/math], так как .

[math] \Longleftarrow [/math]:

Пусть , тогда вычислимо по определению.

Теорема:

Пусть числа вычислимы. Тогда также вычислимы числа , , и .

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

В пределах этого доказательства будем обозначать функцию-приближение для произвольного вычислимого числа [math] x [/math] как [math] f_x [/math].

Для того, чтобы получить приближение для результата операции, нам нужно выразить функцию-результат через приближения для операндов.

Заметим, что , для произвольных рациональных [math] a, b [/math], значит, в качестве необходимых функций для [math] \alpha + \beta [/math] и [math] \alpha - \beta [/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] b_\beta [/math], очевидно, можно найти за конечное время), то

.

Убедимся в вычислимости числа [math] \frac 1 \alpha [/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] r_n [/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]

Так как , первое слагаемое меньше по выбору , второе — в силу вычислимости , то , и действительно вычисляет требуемое приближение.

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

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

Действительное число называется перечислимым снизу (recursively enumerable number), если множество перечислимо.

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

Действительное число называется перечислимым сверху, если множество перечислимо.

Свойства

Теорема:

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

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

[math]\Rightarrow[/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] A [/math] и [math] B [/math] соответственно.

Если [math] \alpha [/math] рационально, то необходимые (полу)разрешатели строятся тривиально.

В противном случае, так как , то перечислимость множеств и равносильна разрешимости множества , которая, в свою очередь, равносильна вычислимости .

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

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

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

Пусть — некоторое перечислимое, но неразрешимое множество натуральных чисел. Занумеруем его элементы. Последовательностью Шпеккера называется последовательность рациональных чисел, -ный член которой определяется как .

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

Теорема:

Число перечислимо снизу, но невычислимо.

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

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

Допустим теперь, что [math] q [/math] вычислимо.

Пусть . Рассмотрим двоичную запись числа , если ее -ный знак после запятой равен 1, то , иначе — . Мы построили разрешатель для множества . Тем не менее, мы знаем, что — неразрешимое множество, и это невозможно, значит, невычислимо.

Ссылки

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

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