Объектно-ориентированная реализация действительных чисел

Цель лекции: Дать объектно-ориентированную трактовку конструктивных действительных чисел. Показать важность данного понятия для конструирования вычислительных процедур.

Основным понятием вычислительной математики и математики вообще является понятие числа. Способность к счету является фундаментальным свойством человека. Проблема, впрочем, состоит в том, что большинство разделов математики оперирует понятием действительного числа. Однако мы исходим из того, что механически можно выполнять лишь операции с целыми числами $$(\Bbb{N})$$. Под операциями мы понимаем операцию сложения, умножения на -1, а также сравнения двух целых чисел. Поскольку рациональное число представляет собой пару целых чисел (числитель/знаменатель), то эти же операции можно считать механическими и для рациональных чисел $$(\Bbb{Q})$$. Драма человечества состояла в открытии несоизмеримости некоторых величин. С этого момента нам потребовались числа, которые не являются механически обозримыми. С древности были известны некоторые иррациональные числа, такие как $$\sqrt{2}, \pi, e$$. Полноценная теория действительных чисел требует применения методов математического анализа. Наиболее ясное построение действительных чисел основано на пополнении метрического пространства рациональных чисел. Идея этого пополнения состоит в том, что все фундаментальные последовательности рациональных чисел разбиваются на классы эквивалентности. Две фундаментальные последовательности рациональных чисел $$\{a_n\}$$ и $$\{b_n\}$$ объявляются эквивалентными если для любого $$\varepsilon>0$$ существуют такое $$N=N(\varepsilon)$$, что для всех $$p,q>N$$ выполнено неравенство$$|a_p-b_q|<\varepsilon.$$ Теперь с каждым классом эквивалентности фундаментальных последовательностей рациональных чисел связывается некоторый идеальный элемент, называемым действительным (или вещественным) числом.

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

Гипотетическая машина Поста состоит из бесконечной ленты, разбитой на отельные ячейки. Каждая ячейка может быть помечена либо $$0$$, либо $$1$$. Также у машины Поста есть воображаемая каретка, которая в каждый момент может находиться только над одной из ячеек. Каретка управляется согласно программе, которая состоит из шести команд:

Работа машины Поста задается программой, содержащей конечное число команд, и начальной конфигурацией (состояние ленты и положение каретки). Начальная конфигурация должна содержать лишь конечное число ячеек, содержащих $$1$$. Мы будем говорить, что функция $$f(n)$$ натурального аргумента и принимающая натуральное значение, алгоритмически вычислима или просто вычислима для аргумента $$n$$, если существует какая-нибудь машина Поста, что если начальная конфигурация содержит ровно $$n$$ ячеек, содержащих $$1$$, то работа машина обязательно закончится командой $$Stop$$ и в момент остановки на ленте будет ровно $$f(n)$$ ячеек, содержащих $$1$$.

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

Мы часто будем говорить, что последовательность рациональных чисел $$a_n$$ является вычислимой, если существует такая вычислимая функция $$f:\Bbb{N}\to\Bbb{Q}$$, что$$a_n=f(n).$$

Вернемся к вещественным числам. Данное выше определение (и любое другое) вызывает ряд вопросов. В самом деле, любое вещественное число - это класс эквивалентности фундаментальных последовательностей. Во-первых, для любого ли вещественного числа можно построить вычислимую фундаментальную последовательность? Ответ, очевидно, нет! Почему? Потому что множество вещественных чисел имеет мощность континуума, а количество всех алгоритмов (машин Поста) счетно. Во-вторых, даже если у нас есть вычислимая фундаментальная последовательность, то это еще не означает, что мы можем узнать предел этой последовательности.

Введем понятие вычислимой сходимости последовательности. Последовательность $$a_n$$ называется вычислимо сходящейся к числу $$\alpha$$, если существует такая вычислимая функция $$\xi:\Bbb{Q}\to\Bbb{N}$$, что для любого рационального $$\varepsilon>0$$ выполнено$$|\alpha-a_n|<\varepsilon,$$ для любого $$n>\xi(\varepsilon)$$.

Число $$\alpha$$ называется конструктивным действительным числом, если существует вычислимая последовательность рациональных чисел, которая вычислимо сходиться к $$\alpha$$. Можно сказать, что конструктивное действительное число это пара вычислимых функций $$\{a(n),\xi(\varepsilon)\}$$. Можно конструктивное действительное число представить в виде одной вычислимой функции: $$A:\Bbb{Q}\to\Bbb{Q}$$, которая по заданному $$\varepsilon>0$$ вычисляет рациональное число такое, что:$$|\alpha-A(\varepsilon)|<\varepsilon.$$ Именно в таком виде мы и реализуем класс для конструктивного действительного числа.

Реализуем абстрактный класс, который будет заготовкой для классов различных конструктивных действительных чисел.$$\begin{verbatim} abstract class TCR { public TCR() { } public abstract double A(double prec); } \end{verbatim}$$

Разумеется, на компьютере мы можем реализовать лишь некоторое приближение к конструктивному действительному числу. Действительно, переменная $$prec$$, во-первых, не может быть произвольным рациональным числом, а, во-вторых, не с любой точностью мы можем проводить вычисления. И еще заметим, что переменные типа $$double$$ представляют собой некоторое подмножество рациональных чисел.

Возникает естественный вопрос - а какие есть примеры конструктивных действительных чисел, не являющихся рациональными? Конструктивными действительными числами являются, например, $$\sqrt{2}, \pi, e, \sin(1)$$. Для примера реализуем первые два из этих конструктивных чисел. Для вычисления числа $$\pi$$ мы воспользуемся рядом Лейбница:$$\frac{1}{1} - \frac{1}{3} + \frac{1}{5} - \frac{1}{7} + \frac{1}{9} - \cdots = \frac{\pi}{4}$$ Конечно, есть ряды, которые значительно быстрее сходятся к числу $$\pi$$, но мы выбрали ряд Лейбница по причине, что для знакопеременного ряда остаток ряда оценивается через модуль последнего слагаемого частичной суммы.$$\begin{verbatim} class TCPi : TCR { public override double A(double prec) { int n = 1; double res = 0; double an = -1.0; double l = 1.0; do { an = 4.0 / (double)n * l; res += an; l = -l; n += 2; } while (Math.Abs(an) > prec); return res; } } \end{verbatim}$$

Для построение конструктивного действительного числа $$\sqrt{2}$$ мы реализуем метод дихотомии для решения уравнения$$x^2-2=0,\quad x\in[1,2].$$ Вот этот класс.$$\begin{verbatim} class TCSQRT2 : TCR { public override double A(double prec) { double a = 1; double b = 2; double c; while ((b - a) > prec) { c = a + (b - a) / 2.0; if (f(c) > 0) { b = c; } else { a = c; } } return a; } double f(double x) { return x * x - 2.0; } } \end{verbatim}$$

Возникает еще один вопрос, если среди действительных чисел не конструктивные действительные числа, то значит есть (и их континуум!) неконструктивных действительных чисел. А есть ли пример такого числа? Но на бумаге невозможно описать неконструктивный объект - можно лишь доказать (неконструктивно) его существование.

Заметим, что в рамках конструктивной математики работать с конструктивными действительными числами весьма сложно. Например доказывается теорема о том, что для произвольного конструктивного действительного числа нет алгоритма, позволяющего определить равно это число нулю или нет. В частности, в рамках конструктивных действительных чисел простейшее линейное уравнение$$ax=b$$ неразрешимо.

Однако есть операции для конструктивных действительных чисел, которые являются алгоритмически разрешимыми, например сложение двух конструктивных чисел. Реализуем соответствующий класс$$\begin{verbatim} class TCRAdd : TCR { TCR CR1, CR2; public TCRAdd(TCR CR1, TCR CR2) : base() { this.CR1 = CR1; this.CR2 = CR2; } public override double A(double prec) { return CR1.A(prec / 2.0) + CR2.A(prec / 2.0); } } \end{verbatim}$$

Ключевые термины

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

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

Машина Поста - гипотетическая вычислительная машина, эквивалентная машине Тьюринга.

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

Краткие итоги: Введено фундаментальное понятие конструктивного действительного числа. Дано уточнение понятия алгоритма с помощью машины Поста. С помощью объектно-ориентированного подхода реализованы классы конструктивных действительных чисел.