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

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

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

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

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

Свойства

Теорема:

Число вычислимо множество разрешимо.

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

[math] \Longrightarrow [/math]

Если — рациональное, то существует тривиальный разрешитель для , который просто сравнивает полученный элемент с .

В противном случае, построим разрешитель для :

function [math] p(x)[/math]:
  for [math] n = 1[/math] to [math]\infty [/math]
    if [math] x \lt  a(\dfrac{1}{n}) - \dfrac{1}{n} [/math]
      return 1
    if [math] x \gt  a(\dfrac{1}{n}) + \dfrac{1}{n} [/math]
      return 0

[math] \Longleftarrow [/math]:

Построим функцию

function [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]:

Если число — рациональное, то необходимую последовательность можно получить, воспользовавшись стандартным алгоритмом перевода числа в двоичную систему счисления. Рассмотрим случай, когда .

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

Напишем программу, которая по числу вычисляет -ный знак после запятой в двоичном представлении числа :

function [math]p(n)[/math]:
  l = 0, r = 1
  for [math] k = 1[/math] to [math]n [/math]
    [math] m = \dfrac{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] \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] \dfrac \varepsilon 2 [/math], поэтому [math] f_{\alpha \pm \beta} [/math] не превосходит [math] \varepsilon [/math]).

Далее, так как

,

где [math]b_\beta[/math] — наименьшее рациональное число, большее [math]\beta[/math] по модулю (т.е. ), то

.

Убедимся в вычислимости числа [math] \dfrac 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] N(\varepsilon_1) [/math], [math] r(n) [/math] и все [math] p_n(\varepsilon_2) [/math] вычислимы.

Построим функцию [math] a(\varepsilon) [/math], которая дает приближение к [math] \alpha [/math] с точностью до [math] \varepsilon [/math]:

function [math] a(\varepsilon) [/math]:
  n = [math] N(\dfrac \varepsilon 2) + 1 [/math]
  return [math] p_n(\dfrac \varepsilon 2) [/math]

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

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

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

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

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

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

Свойства

Теорема:

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

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

[math]\Longrightarrow[/math]:

По определению , множество перечислимо. Кроме того, .

По определению нижней грани, . Тогда можно взять, например, последовательность .

[math]\Longleftarrow[/math]:

Построим полуразрешитель для множества :

function [math]p(x)[/math]:
  for n = [math]1[/math] to [math]\infty[/math]
    if [math] x \lt  a_n [/math]
      return 1

Если , то , и так как , то программа вернет ответ при .

Теорема:

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

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

Обозначим множества и за [math] A [/math] и [math] B [/math] соответственно.

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

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

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

Множество всех программ счётно, поэтому множество вычислимых чисел также счётно. Однако, множество вещественных чисел несчётно, значит, существуют невычислимые вещественные числа. Построим явно пример такого числа.

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

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

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

Теорема:

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

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

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

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

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

Источники информации

Верещагин Н. К., Шень А. — Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции — М.: МЦНМО, 1999 — стр. 14
Computable number
Specker sequence

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