12. Об алгоритмической полноте средств аналитической геометрии

С выходом в свет в 1637 году «Геометрии» Декарта было положено начало новому научному направлению — аналитической геометрии. В основе предложенного Декартом метода координат лежит идея соответствия между геометрическими и алгебраическими объектами. Точке в пространстве (геометрическому объекту) ставится в соответствие тройка чисел (алгебраический объект) и, наоборот, всякой тройке чисел может быть поставлена в соответствие определённая точка пространства. Множеству всевозможных троек чисел соответствует все трехмерное пространство.

Каждый находящийся в пространстве объект может рассматриваться как некоторая совокупность точек, организованная характерным для данного объекта образом. Задание геометрического объекта состоит в указании правила, позволяющего установить, принадлежит или не принадлежит произвольно взятая точка пространства рассматриваемому объекту. Это правило можно представить в виде некоторого предиката принимающего значение истинности в точках данного объекта и значение ложности — вне его.

Пример 1. Используя обозначения, принятые в гл. 1, 9, напишем предикат, соответствующий внутренности сферы радиуса R с центром в начале координат в. виде

Пример 2. Прямой, представленной в виде пересечения двух плоскостей, соответствует предикат

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

В соответствии с этим приходим к двум основным задачам аналитической геометрии:

1. Аналитическому описанию данных геометрических объектов.

2. Исследованию геометрических объектов, соответствующих данным предикатам (уравнениям, неравенствам и др.).

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

Поэтому в XVII—XVIII вв. в центре внимания оказалась задача изучения линий и поверхностей, описываемых заданными уравнениями. Эти исследования подготовили открытие дифференциального и интегрального исчислений. Здесь в первую очередь следует указать на задачи о проведении касатедьных

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

Рассмотрение новых типов уравнений позволило существенно пополнить запасы изученных линий и поверхностей. Тем самым в какой-то мере решалась и первая основная задача, так как этого запаса оказалось достаточно для удовлетворения нужд практики. Самостоятельно первая основная задача ставилась и решалась лишь для небольшого числа наиболее простых геометрических форм: прямой, плоскости, окружности, конических сечений и некоторых других объектов. Общим для всех этих объектов оказалось то, что они описываются уравнениями вида где есть полином относительно двух или трех переменных (в зависимости от того, рассматривается ли линия на плоскости или поверхность в пространстве).

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

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

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

Пусть есть какой-либо набор лекал определяемых в некотором начальном положении уравнениями

соответственно. Функции предполагаются -реализуемыми с базисной системой

где определенные и непрерывные всюду на плоскости функции.

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

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

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

Определение. Базисная система называется алгоритмически полной, если:

а) из принадлежности чертежа к множеству 31 следует принадлежность к множеству всякого чертежа, который может быть совмещен с с помощью преобразований переноса и поворота;

б) из принадлежности чертежа к множеству следует принадлежность к множеству всякого элемента чертежа

в) из принадлежности чертежей к множеству следует принадлежность к множеству чертежа, представляющего собой объединение чертежей

Теорема 1. Базисная система

является алгоритмически полной.

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

Остается показать, что элементы -реализуемых чертежей также -реализуемы. Пусть есть уравнение -реализуемого чертежа есть -реализуемая область, определяемая неравенством Область выделяет из чертежа некоторый элемент Тогда, согласно формуле (3.100)

является уравнением элемента Очевидно, что функция является -реализуемой функцией, и, следовательно, элемент является -реализуемым чертежом.

Теорема 2. Базисная система состоящая из функций является алгоритмически полной.

Справедливость теоремы следует из того, что функция является -реализуемой.

Теорема 3. Базисная система является алгоритмически полной.

Теорема 3 является следствием теоремы 2.

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

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

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