§ 12.12. Рекурсивные действительные числа

Понятие о рекурсивном действительном числе выводится в конструктивной математике.

Конструктивное направление в математике возникло в связи со стремлением избежать противоречий («антиномий»). Оно связано с требованием считать доказательство исчерпывающим, когда не только установлен какой-либо математический факт, но и показано, что соответствующие математические объекты могут быть фактически подсчитаны.

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

Рассмотрим в качестве примера конструктивную формулировку одной часто встречающейся схемы.

В анализе часто встречается высказывание вида «для всякого малого существует такое число N, что некоторая величина, зависящая от , при становится меньше ».

Каков будет конструктивный вариант этой схемы? Для его построения необходимо:

1) Уточнить, что мы будем понимать под «всяким малым ». Примем, например, — как угодно большое целое положительное число.

2) Надо, чтобы по (т. е. по ) существовал способ эффективно определять число .

Поэтому эффективная формулировка рассматриваемой схемы будет такова: «существует такая общерекурсивная функция , что некоторая величина, зависящая от , становится при меньше .

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

Назовем последовательность рациональных чисел

рекурсивной, если существуют такие общерекурсивные функции , что

Будем говорить, что эта последовательность сходится рекурсивно (или эффективно), если существует общерекурсивная функция такая, что для любого как угодно большого

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

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

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

Такой специальной последовательностью является факториальное разложение

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

Обратим внимание также на то, что рекурсивных действительных чисел не больше, чем общерекурсивных функций, т. е. счетное множество; всех же действительных чисел — континуум. В этом смысле лишь незначительная часть действительных чисел рекурсивна.

Рекурсивное действительное число — это фактически такое число, для вычисления которого с любой степенью точности имеется алгоритм. Все обычно рассматриваемые в анализе числа (например и т. д.) являются рекурсивными действительными числами.