14. Вычислимые вещественные числа

Конструктивная точка на вещественной прямой будет называться вычислимым вещественным числом.

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

мы можем найти его окрестноеть такую, что или

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

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

Отношения порядка между вычислимыми вещественными числами вводятся следующим образом.

если мы можем найти окрестность I точки а и окрестность точки такие, что правый конец I меньше левого конца

если для всех окрестностей I точки а и точки левый конец I меньше, чем правый конец Теперь очевидны следующие эквивалентности: тогда и только тогда, когда или тогда и только тогда, когда Первое определение понятия вычислимого вещественного числа было дано Тьюрингом [2]. Согласно ему, вещественное число вычислимо, если оно может быть представлено в виде

где бинарная последовательность

вычислима на машине Тьюринга. Разумеется, с конструктивной точки зрения вычислимое вещественное число есть не что иное, как сама машина Тьюринга.

Если последовательность вычислима на машине Тьюринга, то она рекурсивна и потому определяет вычислимое вещественное число в смысле нашего определения. Обратно, данное вычислимое вещественное число нетрудно представить в указанном выше виде посредством рекурсивной бинарной последовательности. Чтобы завершить доказательство эквивалентности нашего и тьюринговского определений, достаточно таким образом показать, что любая рекурсивная бинарная последовательность вычислима на машине Тьюринга. Как замечено в связи с тезисом Чёрча, это действительно так, хотя мы и не прилагали усилий, чтобы доказать это.